CF538B题解

what_can_I_do · 2023-08-03 22:25:46 · 题解

传送门

这道题一眼 dp。

这一题感觉跟这一题有点像。我们可以先预处理出所有只包含 0 和 1 且不大于 n 的数，存在数组 v。接下来就是 dp。我们先想好 dp_i 表示什么，很容易想到，dp_i 表示加到 i 时使用的数的最少数量。这一题就是一个选与不选的问题。是否要选择加上 v_j 这个数来使其从 i-v_j 变为 i，代价为 1。那么这一题的状态转移方程就可以推出了：dp_i=min(dp_i,dp_{i-v_j}+1)。接下来想 dp 数组的初始状态。由于是最小值，所以先把 dp_i 设成一个很大的数。接下来我们想，0 怎么加才能实现变为 0，很明显，不用加，所以 dp_0=0。那么最后要输出的答案呢，明显的，是 dp_n。

接下来想怎么样实现输出构造方案。可以用一个 vector<int> pe[1000010] 来实现。其中每个 pe_i 表示加到 i 的最优方案。为什么不用数组，因为数组的方案转移要 O(n) 的时间复杂度，但是 vector 只要 O(1)，只需要写成 pe[i]=pe[i-v[j]] 就行了。

现在我们要稍微改一下状态转移方程。我们要把 dp_i=min(dp_i,dp_{i-v_j}+1) 改成 if(dp[i]>dp[i-v[j]]+1) 接下来再跟上 dp[i]=dp[i-v[j]]+1;，然后再将方案转移，pe[i]=pe[i-v[j]]，最后在后面放入新的选择 pe[i].push_back(v[j]) 就行了。

还有，预处理就不用我讲了吧，直接模拟。

CODE:

#include<bits/stdc++.h>
using namespace std;
int n,v[200],l=0,dp[1000010]={0};
vector<int> pe[1000010];
int main()
{
    scanf("%d",&n);
    for(register int now=0;now<=n;)
    {
        v[l]=now,l++;
        now++;
        int s=1;
        while((now%(int(pow(10,s))))/(int(pow(10,s-1)))==2) s++,now=now-2*int(pow(10,s-2)),now+=int(pow(10,s-1));
    }
    l--;
    for(register int i=1;i<=n;i++) dp[i]=999999999;
    for(register int i=0;i<=n;i++)
        for(register int j=0;j<=l;j++)
            if(i>=v[j])
                if(dp[i]>dp[i-v[j]]+1)
                {
                    dp[i]=dp[i-v[j]]+1;
                    pe[i]=pe[i-v[j]];
                    pe[i].push_back(v[j]);
                }
    printf("%d\n",dp[n]);
    for(register int i=0;i<=pe[n].size()-1;i++) printf("%d ",pe[n][i]);
    return 0;
}