首页 > 代码库 > bzoj 1068: [SCOI2007]压缩 DP
bzoj 1068: [SCOI2007]压缩 DP
1068: [SCOI2007]压缩
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 496 Solved: 315
[Submit][Status]
Description
给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。 bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程：
另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。
Input
输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。
Output
输出仅一行，即压缩后字符串的最短长度。
Sample Input
bcdcdcdcdxcdcdcdcd
Sample Output
12
HINT
在第一个例子中，解为aaaRa，在第二个例子中，解为bMcdRRxMcdRR。
【限制】
100%的数据满足：1<=n<=50 100%的数据满足：1<=n<=50
这道题注意转移顺序。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define MAXN 55#define INF 0x3f3f3f3finline void deal(int &x,int y){ if (x>y)x=y;}char str[MAXN];int dp[MAXN][MAXN];//已经做完第i个，在第j个后有一个M,需要的字符个数（包括j处的M）int main(){ //freopen("input.txt","r",stdin); scanf("%s",str+1); int n=strlen(str+1); int i,j,k; int x,y; memset(dp,INF,sizeof(dp)); dp[0][0]=0; bool flag=0; for (i=1;i<=n;i++) { for (j=0;j<=i;j++) if (j<=i-1) { deal(dp[i][j],dp[i-1][j]+1); deal(dp[i][i],dp[i][j]+1); } for (j=i-2;j>=0;j-=2) { x=j+1,y=j+1+(i-j)/2; flag=true; for (k=0;k<(i-j)/2;k++) { if (str[x+k]!=str[y+k]) { flag=false; break; } } if (flag) { deal(dp[i][j],dp[y-1][j]+1); deal(dp[i][i],dp[i][j]+1); } } } int ans=INF; for (i=0;i<=n;i++) { ans=min(ans,dp[n][i]); } printf("%d\n",ans);}
bzoj 1068: [SCOI2007]压缩 DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。