CF1619C Wrong Addition 题解

似乎没人写记忆化搜索的，我就来一波（当然，写动态规划也是可以的，毕竟记忆化搜索只是动态规划的递归形式，不过蒟蒻太菜了，只想到搜索，而没有一开始就想到动规）。

我们把加法转化成减法，开始分割数字 /(c/)，枚举情况。由于 /(b/) 是十进制的，所以 /(c/) 的每一段都由一个或两个数字组成（把这一段组成的数减去 /(a/) 对应的数字，就能算出 /(b/) 这一位是多少），至于判别条件很容易想到，详见代码。

为了保险起见，我还加了个记忆化，这样对于不行的情况，遇到可直接剪枝（其实这种橙题根本不需要记忆化，当然写都写了，我也不把它删除）。

Code:

#include<bits/stdc++.h>
#define ll long long
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x7fffffff
#define v e[i].y
using namespace std;
inline ll read(){
    char ch=getchar();ll x=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();return x*w;
}
inline void write(ll x){
	if(x<0)x=-x,putchar('-');
    if(x<10){putchar(48+x);return;}
    write(x/10),putchar((x+10)%10+48);
}
ll T=read(),a,c,aa[25],cc[25],at,ct,ans[25],t;
bool dp[25][25];
bool dfs(int x,int y){//x:c,y:a
    if(x==ct)return y>=at?1:(dp[x][y]=0);
    if(dp[x][y]==0)return 0;
    if(cc[x+1]-aa[y+1]>=0&&cc[x+1]-aa[y+1]<10){
        ans[++t]=cc[x+1]-aa[y+1];
        if(dp[x+1][y+1]=dfs(x+1,y+1))return 1;
        t--;
    }
    if(x<=ct-2&&cc[x+2]!=0&&cc[x+2]*10+cc[x+1]-aa[y+1]>=0&&cc[x+2]*10+cc[x+1]-aa[y+1]<10){
        ans[++t]=cc[x+2]*10+cc[x+1]-aa[y+1];
        if(dp[x+2][y+1]=dfs(x+2,y+1))return 1;
        t--;
    }
    return dp[x][y]=0;
}
int main(){
    while(T--){
        memset(aa,0,sizeof(aa));
        memset(cc,0,sizeof(cc));
        for(int i=0;i<=23;i++)for(int j=0;j<=23;j++)dp[i][j]=1;
        a=read(),c=read(),at=ct=t=0;
        while(a)aa[++at]=(a+10)%10,a/=10;
        while(c)cc[++ct]=(c+10)%10,c/=10;
        if(dfs(0,0)){
            while(t&&ans[t]==0)t--;
            if(t==0)ans[++t]=0;
            for(int i=t;i>=1;i--)putchar(ans[i]+48);
        }
        else printf("-1");
        putchar('/n');
    }
    return 0;
}