题目链接：CF339C
这题已经有较为完善的题目翻译。在我之前的一篇题解思路是暴力搜索（复杂度是正确的），而这篇题解用的是动态规划的思路。
题目大意
你被允许使用1..10中的若干个数。
一开始有两个数a,b，初始值均为0。
你需要对这两个数交替操作（先操作哪个无关紧要），一共 m次。每次操作你需要将所操作的数加上 一个 你 被允许使用 的数。每次操作需要满足：
- 加上的数和你 上一次 操作不同（对于第一次操作，没有限制）
- 操作后被操作的数必须 严格大于 另一个数
问你是否可能合法地进行m次操作。如果可能，需要构造出一种方法。
1 \leq m \leq 1000
由于动态规划的路径记录实际上非常简单，我们暂且不考虑构造出一种方案，只考虑是否有可能。
状态设计
最容易想到的状态设计是：
dp[1..m][1..10\cdot m][1..10\cdot m]，其中dp[i][j][k][t]表示已经操作i次，并且此时a的值为j，b的值为k，并且上一次操作加上的数是t时，是否有可能。
然而根据题目的数据范围，要开的数组是：dp[1..1000][1..10000][1..10000][1..10]，显然不可以。
我们注意到上面的状态设计中存在极多的冗余信息。我们发现，影响下一步决策的只有：
- 上一次 操作时加上的数（因为这次就不能再用了）
- 上一次 操作后，被操作数减去另一个数所得的值（本次操作加的数必须大于这个）
那么只需将这两个作为状态即可。
- 第一维：0..n，i表示在第i次 操作后。取值范围分析： 理论上需要1..n，而具体实现时，我们需要增加一个0，表示未进行任何操作。这样可以降低编程难度（或避免复制粘贴代码）
- 第二维：0..10，本次操作加上的数（即，下次操作 不能再用的数）。取值范围分析： 加上的数取值范围是1..10，而在没有进行任何操作时，我们认为上次加上的数是0，表示没有任何一个数不能在下一次使用。
- 第三维：0..10，本次操作后，被操作数减去另一个数的值（假如操作的是a，那么这个值就是a-b，否则是b-a）。下一次操作 加上的数必须大于这个。取值范围分析： 每次操作后，这一维的取值范围为1..9。特别地，如果第一次操作加上的是10，那么这一维能取到10。在没有进行任何操作时，我们令这一维为0，表示对下一次操作加上的数的最小值没有限制。
状态描述：dp[i][cant][gt]
我们在dp数组中用0描述“不能做到”，1描述“可以做到”。
利用这种状态设计，我们甚至不用关心本次操作的是哪个数了。
初始化
没有进行任何操作的情况是 可能做到的（显然）。
没有任何操作时，令cant = 0表示下一次（第一次）没有不能取的值，令gt = 0表示对下一次加的数的最小大小没有限制。
对于i=0的其他状态，不能做到。
对于i>1的其他状态，都是未知情况。由于dp是基于“或”操作的（即，能够转移到当前状态的状态只要有一个可能做到，当前状态就可以做到），因此初始化为0。
初始化：
dp[0][0][0] = 0
其他情况都是赋值为0，如果开的是全局数组则会自动初始化为0，无需手动初始化。
状态转移
我们用has[num]表示你是否允许使用数字num。
考虑状态dp[i-1][cant][gt]，那么该状态可以转移到dp[i][num][num-gt]，其中num满足has[val]\ \&\&\ num\ =\not\ cant\ \&\&\ num > gt。
这非常好理解。至于为什么转移到的是num-gt：
假设第i-1操作的数是a，那么gt = a-b。
第i次操作的数应该是b，则有：
gt_{new}
= b_{new} - a_{new}
= (b+num)-a
= num + (b-a)
= num - (a-b)
= num - gt
记录路径
普通的动态规划是很容易记录路径的。我们在更新一个状态时，可以顺便在这个状态中存储 转移到这个状态的前一个状态。
最终dp完成时，由于答案并不关心最后一次操作完成后的cant和gt值，我们需要在dp[n][0..10][0..10]任意取出一个可以做到的值（即，dp[n][0..10][0..10]=1）。
然后根据存储的“上一个状态”向前回溯，并重新计算出每次加上的数，放入一个数组。
由于我们对于一次操作，有gt_{new} = num - gt，可以得出：
如果dp[i][cant_{new}][gt_{new}]由dp[i-1][cant][gt]转移而来，那么第i次操作加上的数put_i就是gt_{new} + gt
最后输出答案即可。
程序与细节注释
// status: [Accepted]
// oj: [luogu]
#include<bits/stdc++.h>
using namespace std;
int has[11]; // 是否允许使用某个数
int put[1001]; // 放入的数，用于最后回溯并输出答案的时候
int n; // 需要操作的次数
struct State {
// 状态
bool can;
// 来历
int p1;
int p2;
int p3;
}dp[1001][11][11];
//DP维度：
// 1. 填充长度
// 2. 不能填充的数字 (0:没有限制)
// 3. 至少填充的数字 (0:没有限制)
int main() {
ios::sync_with_stdio(false);
for(int i=1;i<=10;i++) {
char c;
cin>>c;
has[i] = c-'0';
}
cin>>n;
// 初始化
dp[0][0][0].can = 1;
// 枚举操作次数
for(int i=1;i<=n;i++) {
// 针对 上一个状态：上一次加上的数
for(int cant=0;cant<=10;cant++) {
// 针对 上一个状态：上一次操作后，操作数减去另一个数的值
for(int gt=0;gt<=10;gt++) {
// 上一个状态 不能做到，不进行转移。
if(!dp[i-1][cant][gt].can) continue;
// 枚举大于gt的数用来加
for(int num=gt+1;num<=10;num++) {
// 和上一次冲突，或本来就不能取
if(!has[num] || num==cant) continue;
// 此处使用引用来表示下一次可以转移到的状态，能够简化代码
State &ret = dp[i][num][num-gt];
// 上一个状态有解，当前肯定有解
ret.can = 1;
// 记录状态的“来历”
ret.p1 = i-1;
ret.p2 = cant;
ret.p3 = gt;
}
}
}
}
int c1 = 0, c2 = 0, c3 = 0;
for(int i=0;i<=10;i++) {
for(int j=0;j<=10;j++) {
// 随便找一个有解的状态。
if(dp[n][i][j].can) {
c1 = n;
c2 = i;
c3 = j;
break;
}
}
}
// 有解
if(c1 || c2 || c3) {
cout<<"YES"<<endl;
// 向前回溯，存储答案
while(c1>0) {
State &curr = dp[c1][c2][c3];
int n1 = curr.p1;
int n2 = curr.p2;
int n3 = curr.p3;
// 依据：put[i] = gt_new +gt
put[c1] = c3 + n3;
// 向前跳到上一个状态
c1=n1;c2=n2;c3=n3;
}
// 输出答案
for(int i=1;i<=n;i++) {
if(i>1) cout<<' ';
cout<<put[i];
}
cout<<endl;
}
// 无解
else {
cout<<"NO"<<endl;
}
}
评测记录：R24108985
Comments | NOTHING