T1 序列 [贪心，模拟]
Description
给定一个序列，每次可以将一个数减一，求让所有数字互不相同的最小操作数，\(0\) 除外，也就是 \(0\) 可以相同。
Solution
贪心地，从大到小考虑每个数，都只需要减到第一个没有数出现的数。
开个桶从大到小累计答案即可。
T2 XYD [构造]
Description
给定 \(n\)，构造一个长度不超过 \(6000\) 且仅含 X Y D 三个字母的字符串，使得子序列 XYD 恰好出现 \(n\) 次。
Solution
对于每个 X，假设后面有 \(k\) 个 YD，那么它们产生的贡献是 \(\sum_{i=1}^k i\)。
于是我们可以把 \(n\) 拆成许多个数的阶加即可。
可以选择最大到 \(2000\) 的阶加，如果过大那么字符串长度可能超过 \(6000\)。
T3 大 [状压DP]
Description
初始序列 x 和 y，有 \(m\) 个操作序列 a，每次操作可以把 x 每一个元素变为 \(\max(x_i,a_i)\) 或对 y 进行同样操作。
最大化 \(\sum \max(x_i,y_i)\)。
Solution
考虑每一位，假设它的操作是独立的，那么我们肯定贪心地每一位选最大的是最优的。
但是一个序列只能对 x 和 y 其中一个操作，不能同时操作两个，所以这便涉及到最优分配。
为了方便处理，我们可以把取最大值的操作转换为赋值操作，也就是取一堆最大值，相当于把一个最大的直接赋值给它，考虑哪些位上被赋值，哪些位保留。
综上，要考虑到赋值哪些位，还要考虑到赋值给 x 或 y，于是我们选择 dp 求解。
设 \(f_x(i,j)\)，\((1\le i\le m)\)，\((0\le j\le 2^{2n})\) 表示考虑前 \(i\) 个操作序列，现在是第 \(i\) 个，赋值状态为 \(j\)，且赋值给 x，所能取到的最大答案。\(f_y(i,j)\) 同理。
显然直接转移状态数是会炸的。
但是，每一位我们只需要考虑前 \((n+1)\) 大的，因为最坏的情况就是，x 想要的都被 y 抢走更优，那么 y 最多能占用 \(n\) 个，\(x\) 选第 \((n+1)\) 个即可。然后又因为一共有 \(n\) 位，所以状态数最多只有 \(O(n(n+1))\)。dp 的复杂度为 \(O(n(n+1)2^{2n})\)，非常正确的时间复杂度。
然后空间上，把第一维滚掉即可。
dp 伪代码：
for(int i : 1 ~ m){
for(int j : 1 ~ n){
if(id[i][j] <= n + 1){ // 每位只考虑前 (n + 1) 个
for(int k : 1 ~ 2^2n){
if(第 j 位被选了){
fx[k] = max(fx[k], fx[k ^ (1 << (j - 1))] + a[i][j]);
}
}
for(int k : 1 ~ 2^2n){
if(第 j 位被选了){
fy[k] = max(fy[k], fy[k ^ (1 << (j + n - 1))] + a[i][j]);
}
}
}
}
// 合并答案 滚动数组
fx[] = fy[] = max(fx[], fy[]);
}
// 把没赋值的加上原来的值
for(int i : 1 ~ 2^2n){
for(int j : 1 ~ n){
if(第 j 位没被赋值){
fx[i] += x[j];
}
}
for(int j : n+1 ~ 2n){
if(第 j 位没被赋值){
fx[i] += y[j];
}
}
}
ans = max{fx[]}; // 用 fy[] 也行，因为已经合并了
Summary
DP 好题，把取 \(\max\) 转化为了赋值，并巧妙利用了题目 \(n\) 的数据范围。
标签：le,序列,操作,XYD1004CSPS,考虑,dp,赋值 From： https://www.cnblogs.com/chenwenmo/p/18453950