题目描述
A multi-digit column addition is a formula on adding two integers written like this:
A multi-digit column addition is written on the blackboard, but the sum is not necessarily correct. We can erase any number of the columns so that the addition becomes correct. For example, in the following addition, we can obtain a correct addition by erasing the second and the forth columns.
Your task is to find the minimum number of columns needed to be erased such that the remaining formula becomes a correct addition.
输入
There are multiple test cases in the input. Each test case starts with a line containing the single integer n, the number of digit columns in the addition (1 ⩽ n ⩽ 1000). Each of the next 3 lines contain a string of n digits. The number on the third line is presenting the (not necessarily correct) sum of the numbers in the first and the second line. The input terminates with a line containing “0” which should not be processed.
输出
For each test case, print a single line containing the minimum number of columns needed to be erased.
样例输入
3
123
456
579
5
12127
45618
51825
2
24
32
32
5
12299
12299
25598
0
样例输出
0
2
2
1
题意：给出数字的位数n，给出三个位数为n的数字，表示数值a+数值b=数值c，以竖式计算的形式给出。现判断这个竖式是否成立，输出使得该竖式成立删除的最少位数。
对于三个数值，用字符串表示，我们可以用DP求出使该竖式成立保留的最长位数，用原竖式长度减掉最长长度即可。
对于竖式的每一位，我们计算当前位下的ai+bi是否等于ci值，注意还应加上该位数的进位。
我们用ax数组表示当前位加和后是否有进位。这样有一个好处就是不需要判断我当前位的加和是否需要进位才能等于ci位，直接加上该加上的两位和进位判断即可。对于有进位的情况，我们减去10，因为最大加和不会超过18，减去10即可得到个位数字，直接与ci相比较。
对于数位上的每一个数字，我们计算了两者的求和结果，并且得知了该位是否有进位，这样预处理之后，我们计算在当前遍历的长度下，最长可延续的位数是多少，并在此过程中不断更新要求解的最长长度值。
在内层循环中，遍历已经处理好的所有位数，我们将利用处理好的前i个值计算出dp【i】可以得到的最长正确位数。每次取遍历的dp【j】，判断dp【j】保存的长度是否能增长i的长度，若可以，判断加上j位的进位(如果有的话)后是否能仍然等于c【i】。若满足了这些条件即可更新出dp【i】的最长值。对于更新出来的新的dp【i】我们有两种处理情况，如果有进位，那么更新第i位的进位ax i 。并且如果没有进位，说明可以作为最终位(最后的最高位不可能有进位)，那么用其更新ans。这样不断更新长度为i的最长可行解。
注意此题中最低位是数组中的n-1位，最高位是数组中的0位
#include<bits/stdc++.h>
using namespace std;
const int maxn=1050;
char a[maxn],b[maxn],c[maxn];
int aa[maxn],bb[maxn],cc[maxn],ax[maxn],dp[maxn],n;
int main()
{
while(scanf("%d",&n)&&n)
{
memset(dp,0,sizeof(dp));
memset(ax,0,sizeof(ax));
scanf("%s %s %s",a,b,c);
for(int i=0; i<n; i++)
{
aa[i]=a[i]-'0';
bb[i]=b[i]-'0';
cc[i]=c[i]-'0';
}
int ans=0;
for(int i=n-1; i>=0; i--)
{
if((ax[i]+aa[i]+bb[i])%10==cc[i])
{
if((ax[i]+aa[i]+bb[i])/10==0)
{
dp[i]=1;
ans=max(ans,dp[i]);///必须更新当前预处理出来的dp长度作为ans
}
else dp[i]=1,ax[i]=1;
}
for(int j=n-1;j>i;j--)
{
if(aa[i]+bb[i]+ax[j]==cc[i]&&dp[i]<dp[j]+1)
{
dp[i]=dp[j]+1;
ans=max(ans,dp[i]);
}
if(aa[i]+bb[i]+ax[j]-10==cc[i]&&dp[i]<dp[j]+1)
{
dp[i]=dp[j]+1;
ax[i]=1;
}
}
}
// for(int i=0;i<n;i++)printf("--%d
",dp[i]);
printf("%d
",n-ans);
}
}