T1 能量项链

区间 dp

solution

首先我们可以把每个珠子给求出来。第 $i$ 个珠子显然为 $(p_{i - 1} , p_{i})$，特别的第 $n$ 个珠子为 $(p_n , p_1)$

因为题目中珠子形成一个环，考虑开二倍破环为链。设 $dp_{i , j}$ 为聚合 $i$ 到 $j$ 颗珠子释放出的能量最大值，有如下转移：

$$dp_{i,j} = \max_{i \leq k < j}(dp_{i , k} + dp_{k + 1 , j} + p_{i-1} p_{k} p_j)$$

注意区间 dp 转移时要注意子区间已被转移，所以我们要先枚举区间长度，再枚举左端点

最后对于每一个 $i$ 到 $i + n - 1$ 的顺序统计最大值即可

code

#include<bits/stdc++.h>
using namespace std;

const int N = 205;

struct node{
	int h , t;
}a[N];

int n , p[N] , dp[N][N] , ans;

int main(){
	cin >> n;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> p[i];
		a[i - 1] = {p[i - 1] , p[i]};
	}
	a[n] = {p[n] , p[1]};
	for(int i = 1 ; i <= n ; i ++){
		a[i + n] = a[i];
	}
	
	for(int l = 2 ; l <= n ; l ++){
		for(int i = 1 ; i <= 2 * n - l + 1 ; i ++){
			int j = l + i - 1;
			for(int k = i ; k < j ; k ++){
				dp[i][j] = max(dp[i][j] , dp[i][k] + dp[k + 1][j] + a[i].h * a[k].t * a[j].t);
			}
		}
	}
	for(int i = 1 ; i <= n ; i ++){
		int j = i + n - 1;
		ans = max(ans , dp[i][j]);
	}
	cout << ans;
	return 0;
}

T2 金明的预算方案

背包 dp

solution

首先若没有附件的话本题就是一个背包板子，设 $dp_{i , j}$ 为当前考虑前 $i$ 件物品，用了 $j$ 块钱的物品重要度之和最大值（这里重要度为题目中物品的价格与重要度的乘积）

显然 $dp_{i,j} = \max(dp_{i - 1 , j} , dp_{i - 1 , j - w_i} + v_i)$

可以用滚动数组优化第一维

下面考虑有附件的情况：

我们可以只枚举主物品，用 vector 列举主物品有哪些附件，在枚举主物品时分类讨论附件，具体地：

1. 不买主物品和附件
2. 买主物品和第一个附件
3. 买主物品和第二个附件
4. 同时买主物品，第一个附件和第二个附件

code

#include<bits/stdc++.h>
using namespace std;

const int N = 65;

int n , m , v[N] , b[N] , w[N] , dp[40000];
vector<int> g[N];

int main(){
	cin >> n >> m;
	
	for(int i = 1 ; i <= m ; i ++){
		int p;
		cin >> w[i] >> p >> b[i];
		v[i] = w[i] * p;
		if(b[i] != 0) g[b[i]].push_back(i);
	}
	for(int i = 1 ; i <= m ; i ++){
		if(b[i] != 0) continue;
		
		for(int j = n ; j >= w[i] ; j --){
			dp[j] = max(dp[j] , dp[j - w[i]] + v[i]);
			
			if(g[i].size() > 0){
				if(j >= w[i] + w[g[i][0]]) dp[j] = max(dp[j] , dp[j - w[i] - w[g[i][0]]] + v[i] + v[g[i][0]]);
				
				if(g[i].size() > 1){
					if(j >= w[i] + w[g[i][1]]) dp[j] = max(dp[j] , dp[j - w[i] - w[g[i][1]]] + v[i] + v[g[i][1]]);
					if(j >= w[i] + w[g[i][0]] + w[g[i][1]]){
						dp[j] = max(dp[j] , dp[j - w[i] - w[g[i][0]] - w[g[i][1]]] + v[i] + v[g[i][0]] + v[g[i][1]]);
					}
				}
			}
		}
	}
	cout << dp[n];
	return 0;
}

T3 作业调度方案

模拟

solution

这道题最大的难点就是看懂题目

我们直接按题目模拟即可：

1. 直接按顺序处理工序
2. 对于每个工序，能够插空就插空，具体地设该工序对应工件的上一道工序完成时间为 $t$，那么直接枚举 $t + 1$ 到上界，若机器有空余时间直接安排该工序
3. 最后统计 $ans$ 即可，$ans$ 为所有工件完成最晚时间

code

#include<bits/stdc++.h>
using namespace std;

const int N = 25;

struct node{
	int a , ti;
};

int m , n , p[N * N] , t[N][N * N] , s[N] , k[N] , ans;
node wk[N][N];

int main(){
	cin >> m >> n;
	
	for(int i = 1 ; i <= n * m ; i ++){
		cin >> p[i];
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			cin >> wk[i][j].a;
		}
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			cin >> wk[i][j].ti;
		}
	}
	for(int i = 1 ; i <= n * m ; i ++){
		s[p[i]] ++;
		
		int a = wk[p[i]][s[p[i]]].a , ti = wk[p[i]][s[p[i]]].ti;
		
		for(int j = k[p[i]] + 1 ; j < N * N ; j ++){
			bool flag = 1;
			for(int h = j ; h <= j + ti - 1 ; h ++){
				if(t[a][h]){
					flag = 0;
					continue;
				}
			}
			if(flag){
				for(int h = j ; h <= j + ti - 1 ; h ++) t[a][h] = 1;
				k[p[i]] = max(k[p[i]] , j + ti - 1);
				break;
			}
		}
	}
	for(int i = 1 ; i <= n ; i ++) ans = max(ans , k[i]);
	cout << ans;
	return 0;
}

T4 2^k进制数

组合数学 + 计数

solution

显然地，一个 $n$ 位的 $2^k$ 进制数转化为 $2$ 进制数后有 $kn$ 位，所以有：

$$\begin{split} kn &\leq w \\ \therefore n &\leq \lceil \frac wk \rceil \end{split}$$

其中最高位可能不满 $k$ 位，当 $w \equiv 0 \pmod k$ 时最高位是 $k$ 位

首先当最高位为 $0$ 时，由题目所求的数 $r$ 至少有 $2$ 位，且每一位严格小于它右边相邻的那一位。所以当我们有 $p$ 位且不为 $0$ 时，每一位有 $[1 , 2^k - 1]$ 种可能，所以答案可以转变为从 $2^k - 1$ 个数中选 $p$ 个数的组合

因为 $r$ 可能有 $2$ 位，$3$ 位 ... $n - 1$ 位，所以把可能加起来，为：

$$cnt = \sum_{i = 2}^{\lfloor \frac wk \rfloor}{\binom{2^k - 1}{i}}$$

注意当最高位为 $k$ 位时不用分类讨论，直接就是这个结果（可以自己想一想为什么）

当最高位不为 $0$ 时，最高位转化为 $2$ 进制数后有 $w \bmod k$ 位，所以最高位有 $[1 , 2^{w \bmod k} - 1]$ 种取值，最高位后面每一位有 $[g + 1 , 2 ^ k - 1]$ 种取值（$1 \leq g \leq 2^{w \bmod k} - 1$） (这里 $g$ 就是最高位当前取值)

一共有 $\lfloor \frac wk \rfloor$ 位，所以枚举最高位的取值，把可能加起来有：

$$\begin{split} cnt' &= \sum_{i = 1}^{2^{w \bmod k} - 1}{\binom{2^k - i - 1}{\lfloor \frac wk \rfloor}} \\ \therefore ans &= \sum_{i = 2}^{\lfloor \frac wk \rfloor}{\binom{2^k - 1}{i}} + \sum_{i = 1}^{2^{w \bmod k} - 1}{\binom{2^k - i - 1}{\lfloor \frac wk \rfloor}} \end{split}$$

递推预处理组合数，再暴力加即可，组合数范围最多 $2^k - 1 \leq 512$，注意用高精度处理（最烦人）

code

#include<bits/stdc++.h>
using namespace std;

const int N = 520;

struct hp {
	int a[205] = {0}, len = 0;

	hp operator =(string s) {
		len = s.length() - 1;
		for (int i = 0 ; i <= len ; i ++) a[i] = s[len - i] - '0';
		return *this;
	}
	hp operator +(hp b) {
		hp ans;
		ans.len = max(len, b.len);
		for (int i = 0 ; i <= ans.len ; i ++) {
			ans.a[i] += a[i] + b.a[i];
			ans.a[i + 1] += ans.a[i] / 10;
			ans.a[i] %= 10;
		}
		if (ans.a[ans.len] > 0) ans.len ++;
		return ans;
	}
};

bool cmp(const hp &a, const hp &b) {
	for (int i = max(a.len, b.len) ; i >= 0 ; i --) {
		if (a.a[i] > b.a[i]) return true;
		if (a.a[i] < b.a[i]) return false;
	}
	return true;
}

void print(hp ans) {
	for (int i = ans.len - 1 ; i >= 0 ; i --) cout << ans.a[i];
}

int w, k;
hp c[N][N] , ans , a , b;

int main() {
	cin >> k >> w;
	
	int t = (1 << k);
	c[0][0] = "1";
	for(int i = 1 ; i < t ; i ++){
		c[i][0] = c[i][i] = "1";
	}
	for(int i = 1 ; i < t ; i ++){
		for(int j = 1 ; j < i ; j ++){
			c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
		}
	}
	
	ans = "0";
	for(int i = 2 ; i <= w / k ; i ++){
		if(i > t - 1) break;
		ans = ans + c[t - 1][i];
	}
	int s = w / k , r = (1 << (w % k));
	for(int i = 1 ; i <= r - 1 ; i ++){
		if(s > t - 1 - i) break;
		ans = ans + c[t - 1 - i][s];
	}
	print(ans);
	return 0;
}