Light OJ 1013 Love Calculator(DP)
2024-10-15 03:54:01
题目大意:
给你两个字符串A,B 要求一个最短的字符串C,使得A,B同时为C的子串。 问C最短长度是多少? C有多少种?
题目分析:
做这道题目的时候自己并没有推出来,看了网上的题解。
1.dp[C串的长度][包含A的字符个数][包含B的字符个数] = 种类数
状态转移:如果 A[i] == B[j] 那么 dp[k][i][j] = dp[k-1][i-1][j-1]. 就是说我最后一个字符是相同的那么我只要放一个就可以了。
如果 A[i] != B[j] 那么 dp[k][i][j] = dp[k-1][i-1][j] + dp[k-1][i][j-1].最后一个字符我们要么放A[i] 要么放 B[j] 就这两种情况了。
然后关于找最短的,就可以在 dp[k][lenA][lenB] 种找到最小的k即可。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
#define Max(a,b) (a>b?a:b)
const int INF = 1e9+;
const int maxn = ;
const int MOD = ;
LL dp[maxn*][maxn][maxn];///dp[总长度][包含i个A串字符][包含j个B串字符]
char A[maxn], B[maxn]; int main()
{
int T, cas = ;
scanf("%d", &T);
while(T --)
{
scanf("%s %s", A, B);
int lenA = strlen(A);
int lenB = strlen(B);
memset(dp, , sizeof(dp));
for(int i=; i<=lenA; i++) dp[i][i][] = ;
for(int i=; i<=lenB; i++) dp[i][][i] = ; for(int i=; i<=lenA+lenB; i++)
for(int j=; j<=lenA; j++)
for(int k=; k<=lenB; k++)
{
if(A[j-] == B[k-])
dp[i][j][k] += dp[i-][j-][k-];
else
dp[i][j][k] += dp[i-][j-][k] + dp[i-][j][k-];
}
int k;
for(k = ; k<=lenA+lenB; k ++)
{
if(dp[k][lenA][lenB])
break;
}
printf("Case %d: %d %lld\n", cas ++, k, dp[k][lenA][lenB]);
}
return ;
}
代码在此
最新文章
- linux解压/压缩文件
- 反人类的MyEclipse之-调整JavaScript代码-花括号换行显示
- 更好的逐帧动画函数 — requestAnimationFrame 简介
- POJ1351 Number of Locks(数学)
- Android 背景图片重复平铺
- hdu 5438 Ponds dfs
- “后PC”时代来临
- Java语言与C++语言的差异总结
- Array.prototype.slice.call(arguments) 类数组转成真正的数组
- Codeforces Round #336 (Div. 1) A - Chain Reaction
- react-native迁移版本遇到的问题
- Android Studio Module疑问
- URL加随机数的作用
- EntityFramework Core Raw Query再叙注意事项后续
- SQL server 用命令行更改数据库
- BZOJ4970 IOI2004 empodia障碍段
- 引用MinGW生成的.dll.a后出现的问题
- 【MySQL】MySQL基础操作语句
- centos安装Django之四:安装Django
- uwsgi+django 配置