UVA1625 线性DP

2019-11-06 09:31:46

字体：大中小

来源：转载

供稿：网友

题意

两个长度为n和m的字符串，将这两个字符串拼接成一个字符串。L为字符串所有字母，末位字母与首字母之差的和。求L的最小值。

题解

设d[i][j]为第一个字符串移走i个元素，第二个字符串移走j个元素后还需要的费用。res[i][j]为第一个字符串移走i个元素，第二个字符串移走j个元素时尚未结束的字母个数。可得状态转移方程dp[i][j]=min(dp[i+1][j],dp[i][j+1])+res[i][j]。

注意事项

需要特别注意，last需要初始化为-1，而不是初始化为0。last初始化为0会影响字母开始与结束的判断，导致结果错误。

代码

#include <iostream>#include<cstdio>#include<algorithm>#include<cstring>#define INF 1e9using namespace std;char ch1[5010],ch2[5010];int res[5010][5010],dp[5010][5010];int len1,len2;void init(){ int start[30][2],last[30][2]; len1=strlen(ch1); len2=strlen(ch2); memset(last,-1,sizeof(last)); for(int i=0;i<30;i++){ for(int j=0;j<2;j++){ start[i][j]=INF; } } for(int i=0;i<len1;i++){ int ch=ch1[i]-'A'; if(start[ch][0]==INF){ start[ch][0]=i; } last[ch][0]=i; } for(int i=0;i<len2;i++){ int ch=ch2[i]-'A'; if(start[ch][1]==INF){ start[ch][1]=i; } last[ch][1]=i; } for(int i=0;i<=len1;i++){ for(int j=0;j<=len2;j++){ int cnt=0; for(int k=0;k<30;k++){ if(start[k][0]==INF&&start[k][1]==INF) continue; if(start[k][0]>i-1&&start[k][1]>j-1) continue; if(last[k][0]<=i-1&&last[k][1]<=j-1) continue; cnt++; } res[i][j]=cnt; } }}int main(){ int kase; scanf("%d",&kase); for(int ks=1;ks<=kase;ks++){ scanf("%s%s",ch1,ch2); init(); dp[len1][len2]=0; for(int i=len2-1;i>=0;i--){ dp[len1][i]=dp[len1][i+1]+res[len1][i]; } for(int i=len1-1;i>=0;i--){ for(int j=len2;j>=0;j--){ if(j==len2) dp[i][j]=dp[i+1][j]+res[i][j]; else dp[i][j]=min(dp[i+1][j],dp[i][j+1])+res[i][j]; } } PRintf("%d/n",dp[0][0]); } return 0;}

上一篇：pjsua_lib示例之简单UA

下一篇：ZOJ3603-Draw Something Cheat

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注