本文主要是介绍Column Addition(DP+思维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题 H: Column Addition
时间限制: 1 Sec 内存限制: 128 MB提交: 198 解决: 38
[ 提交][ 状态][ 讨论版][命题人: admin]
题目描述
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
提示
题意：给你一个竖式的加和，可任意抹去一竖行，问若要使竖式成立，最少需要删去多少行？
题解：对于每一竖行，可枚举是从那一行进位过来的，进位可能是0可能是1，同时用res数组记录到该行最多可保留几行竖式，状态转移方程就是dp[i]=dp[j]+1,类似于最长上升子序列，同时更新最大值的时候要只去更新没有进位的位置。
#include<stdio.h>
#include <algorithm>
#include<iostream>
#include<string.h>
#include<vector>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<deque>
#include<ctype.h>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<algorithm>
#define INF 0x3f3f3f3f
#define gcd(a,b) __gcd(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define FAST_IO ios::sync_with_stdio(false)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
inline ll read(){ll x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f;}char a[1005],b[1005],c[1005];
int res[1005],indx[1005];
int main()
{int n;while(scanf("%d",&n)!=EOF,n){mem(res,0);mem(indx,0);scanf("%s",a+1);scanf("%s",b+1);scanf("%s",c+1);for(int i=1;i<=n;i++){a[i]-='0';b[i]-='0';c[i]-='0';}int ans=0;for(int i=n;i>=1;i--){if(a[i]+b[i]+indx[i]==c[i] || a[i]+b[i]-10+indx[i]==c[i]){res[i]=1;if(a[i]+b[i]+indx[i]==c[i]) indx[i]=0;else indx[i]=1;if(indx[i]==0) ans=max(ans,res[i]);}for(int j=n;j>i;j--){if((a[i]+b[i]+indx[j]==c[i] && res[i]<res[j]+1) || (a[i]+b[i]+indx[j]-10==c[i] && res[i]<res[j]+1)){res[i]=res[j]+1;if(a[i]+b[i]+indx[j]==c[i]) indx[i]=0;else indx[i]=1;if(indx[i]==0) ans=max(ans,res[i]);}}}printf("%d\n",n-ans);}return 0;
}这篇关于Column Addition(DP+思维)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
