AT214 連射王高橋君题解

PosVII · 2021-10-19 23:43:48 · 题解

前言

CSP2021 前的题解。

rp++

思路

看到输出序列，不难想到动态规划实现。即 dp_i 表示凑出 i 这个数字所需要的最少的字符。

而我们可以发现动态规划会有两个缺陷：

空间太大，足足 10^{18}，因此不可行。
难以实现，直接DP不能存储方案

对于第二点，我们可以使用记忆化搜索等效替代，但空间的优化需要我们进行思考。如果是学习了数位DP的同学，肯定发现这道题和数位DP都有一个共同点：需要的数字都太大，我们无法直接存储或进行DP。如果是数位DP，我们会存储下当前位数和上一位的数字。那么我们同样可以将这个思路代入这道题。

于是有对于 dp_{i,j}，它表示当我们在对第 i 位进行计算时当前位的数字之和为 j 时的最短长度。

不难发现，我们最多使用 10 个数字就可以表达一个数。因此 j < 100。

但是，每个数并不只有一位非零，不能一用就抛弃，那么我们新增状态 k 表示之前已经有 k 个数字了，这样我们就可以在不创建新的数字的情况下做出贡献。同时，我们可能已经在当前位使用了一些数字，所以第四个状态也出现了。

那么空间与时间上就完全可行了，相信输出序列对大家并不难。

code

#include<bits/stdc++.h>
using namespace std;
int dp[20][100][12][12];//在看第i位的时候，你还需要凑j，之前已有t个数字，当前位最多有k个没有花费时的最大长度。
int tway[12][20],way[12][20];
int num[20],n,len,ans=INT_MAX;
bool vis[10];
void dfs(int dep,int sum,int free,int u,int res) {
    if(dep==n+1) {
        if(sum!=0) return;
        if(ans>res-(free==1)) {
            len=free;
            ans=res-(free==1);
            for(int i=1;i<=len;++i) {
                for(int j=1;j<=n;++j) {
                    way[i][j]=tway[i][j];
                }
            }
        }
        return;
    }
    if(free>=10) return;
    if(dp[dep][sum][free][u]<=res) return;
    dp[dep][sum][free][u]=res;
    for(int i=0;i<=9;++i) {
        if(i>sum) break;
        if(vis[i]) {
            int las=sum-i;
            if(las<10) {
                if(u==0) {
                    tway[free+1][dep]=i;
                    dfs(dep+1,las*10+num[dep+1],free+1,free+1,res+n-dep+2);
                    tway[free+1][dep]=0;
                }
                else {
                    tway[u][dep]=i;
                    dfs(dep+1,las*10+num[dep+1],free,free,res);
                    tway[u][dep]=0;
                }
            }
            if(u==0) {
                tway[free+1][dep]=i;
                dfs(dep,las,free+1,0,res+n-dep+2);
                tway[free+1][dep]=0;
            }
            else {
                tway[u][dep]=i;
                dfs(dep,las,free,u-1,res);
                tway[u][dep]=0;
            }
        }
    }
}
char str[20]; 
long long tar;
int main() {
    memset(dp,127,sizeof(dp)); 
    cin>>str+1;
    for(int i=strlen(str+1);i>=1;--i) vis[str[i]-'0']=1;
    scanf("%lld",&tar);
    while(tar) {
        num[++n]=tar%10;
        tar/=10;
    }
    for(int i=1;i<=n/2;++i) swap(num[i],num[n-i+1]);
    dfs(1,num[1],0,0,0);
    for(int i=1;i<len;++i) {
        bool fl=0;
        for(int j=1;j<=n;++j) {
            if(!fl&&!way[i][j]) continue;
            fl=1;
            printf("%d",way[i][j]);
        }
        printf("+");
    }
    bool fl=0;
    for(int j=1;j<=n;++j) {
        if(!fl&&!way[len][j]) continue;
        fl=1;
        printf("%d",way[len][j]);
    }
    if(len!=1) printf("=\n");
    return 0;
}

AT214 連射王高橋君 题解

AT214 連射王高橋君题解