本文主要是介绍uva 10069 DP + 大数加法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>#define LL long longusing namespace std;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = 4 * atan(1.0);
const double ee = exp(1.0);const int maxa = 10000 + 10;
const int maxb = 100 + 10;char res[maxb], dp[maxa][maxb][maxb];
char s1[maxa], s2[maxb];void add(char a[], char b[])
{int A[maxb], B[maxb], C[maxb];memset(res, 0, sizeof(res));memset(A, 0, sizeof(A));memset(B, 0, sizeof(B));memset(C, 0, sizeof(C));int lena = strlen(a);int lenb = strlen(b);int len;for (int i = 0; i < lena; i ++)A[lena - i - 1] = a[i] - '0';for (int i = 0; i < lenb; i ++)B[lenb - i - 1] = b[i] - '0';len = max(lena, lenb);for (int i = 0; i < len; i ++){C[i] += A[i] + B[i];C[i + 1] += C[i] / 10;C[i] %= 10;}while (C[len] == 0 && len > 0)len --;for (int i = len; i >= 0; i --){res[len - i] = C[i] + '0';}
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCALint ncase;scanf("%d", &ncase);while (ncase--){scanf("%s%s", s1, s2);int lena = strlen(s1);int lenb = strlen(s2);for (int i = 0; i < lena; i++)strcpy(dp[i][0], "1");for (int i = 1; i <= lena; i++){for (int j = 1; j <= lenb; j++){strcpy(dp[i][j], dp[i - 1][j]);if (s1[i - 1] == s2[j - 1]){add(dp[i][j], dp[i - 1][j - 1]);strcpy(dp[i][j], res);}}}printf("%s\n", dp[lena][lenb]);}return 0;
}
这篇关于uva 10069 DP + 大数加法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
