[洛谷题解] CF339C Xenia and Weights • KMnO4y

题目链接：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;
    }
}

cpp

评测记录：R24108985 ↗