ZUFE2483 DO IT YOURSELF
2483: DO IT YOURSELF
时间限制: 2 Sec 内存限制: 128 MB提交: 8 解决: 3
[ 提交][ 状态][ 讨论版]
题目描述
有四个字符串S,T,tmp,ans,一开始给定S和T,tmp和ans为空字符串
每次可以对S串进行如下三步操作:(每次操作必须按顺序完成如下三步,按顺序完成三步称为一次操作)
第一步:选取S串的一段子串,S[L]…S[R],L<=R
第二步:将tmp串设置为S[L]…S[R],将tmp串拼接到ans串尾部
第三步:将S[0]…S[R]设置为‘*’,将tmp串设置为空字符串
问最少需要几次操作,能使得字符串ans和T相同。
输入
第一行输入一个整数T,表示有T组测试数据
每组测试数据第一行输入字符串S,第二行输入字符串T
1<=|S|,|T|<=1000
S和T串只包含小写英文字母
输出
每组测试数据输出最少操作次数,无解输出2147483647。
样例输入
3 jellydanhao jao jellydanhao ll jellydanhao z
样例输出
2 1 2147483647
提示
来源
周甄陶
——————————————————————————————————————————
首先感谢学长的命题与指导!
思路:dp,dp[i][j]表示a串到i位置b串到j位置完全匹配的最小段数,有点类似于LCS的做法
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>using namespace std;#define LL long long
const int INF=0x3f3f3f3f;char a[1005];
char b[1005];
int dp[1005][1005];int main()
{int T;scanf("%d",&T);while(T--){scanf("%s",a);scanf("%s",b);memset(dp,INF,sizeof dp);int k1=strlen(a);int k2=strlen(b);for(int i=0; i<k1; i++)if(b[0]==a[i])while(i<k1)dp[0][i]=1,i++;for(int i=1; i<k2; i++){int mn=INF;for(int j=i; j<k1; j++){mn=min(dp[i-1][j-1],mn);if(b[i]==a[j]){dp[i][j]=min(dp[i][j],mn+1);if(b[i-1]==a[j-1])dp[i][j]=min(dp[i-1][j-1]==INF?INF:dp[i-1][j-1],dp[i][j]);}elsedp[i][j]=min(dp[i][j-1],dp[i][j]);}}int ans=INF;for(int i=0;i<k1;i++)ans=min(ans,dp[k2-1][i]);printf("%d\n",ans==INF?2147483647:ans);}return 0;
}
更多推荐
ZUFE2483 DO IT YOURSELF
发布评论