[洛谷题解] CF339C Xenia and Weights

题目链接: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的值为jb的值为k,并且上一次操作加上的数是t时,是否有可能。

然而根据题目的数据范围,要开的数组是:dp[1..1000][1..10000][1..10000][1..10],显然不可以。

我们注意到上面的状态设计中存在极多的冗余信息。我们发现,影响下一步决策的只有:

  • 上一次 操作时加上的数(因为这次就不能再用了)
  • 上一次 操作后,被操作数减去另一个数所得的值(本次操作加的数必须大于这个)

那么只需将这两个作为状态即可。

  • 第一维:0..ni表示在第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完成时,由于答案并不关心最后一次操作完成后的cantgt值,我们需要在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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注