CodeForces - 825F(DP)
程序员文章站
2024-03-14 14:16:52
...
题目链接:CodeForces - 825F
题意:将给出的字符串压缩,压缩规则是将重复的循环节压缩成一个循环单位并在循环单位前标上被压缩的循环节的循环单位的的个数,求压缩后的字符串的最小长度。如:aaaaa -> 5a ,所以长度是2;abc -> 1abc ,所以长度是4。
题解:这题要用dp的思想,dp[i]里存的是前i个字符组成的串能被压缩的最小长度,从前往后依次枚举以当前字符为起始的串能被压缩的成的最小串的长度,然后用状态转移方程:
dp[i] = min{dp[i], dp[i - 被压缩串长] + 循环节长 + 循环节个数长}
循环节可以用KMP的next的数组求出,先求出next数组,然后从1开始遍历,对每个位置i,如果i % (i - next[i]) == 0 ,那么i - next[i]就是循环节的长度了。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 8e3 + 10;
char s[maxn];
int dp[maxn];
int nxt[maxn];
void getnxt(char* T, int n)
{
int j = 0, k = -1;
nxt[0] = -1;
while(j < n){
if(k == -1 || T[j] == T[k]) nxt[++j] = ++k;
else k = nxt[k];
}
}
int calc(int x) //计算循环节个数长
{
int res = 0;
while(x){res++; x /= 10;}
return res;
}
int main()
{
while(scanf("%s", s) != EOF){
int n = strlen(s);
memset(dp, INF, sizeof(dp));
dp[0] = 0;
for(int i = 0; i < n; i++){
getnxt(s + i, n - i);
for(int j = i; j < n; j++){
int len = j - i + 1;
int x = len - nxt[len]; //循环节长度
int num = 1; //循环节个数
if(len % x == 0) num = len / x;
dp[j + 1] = min(dp[j + 1], dp[i] + len / num + calc(num));
}
}
printf("%d\n", dp[n]);
}
return 0;
}
上一篇: Java字符串的GZIP压缩和解压
下一篇: 9、张龙netty学习Grpc
推荐阅读
-
CodeForces - 825F(DP)
-
CodeForces 825F String Compression---这个KMP很DP
-
cf Educational Codeforces Round 25 F. String Compression
-
Codeforces 825F - String Compression
-
【转】cf 825F - 19 String Compression 【kmp+dp】
-
codeforces 825F (简单dp + KMP)
-
Codeforces 825F String Compression DP(最小循环节)
-
Codeforces #345div1 C Table Compression (650C) 并查集
-
codeforces Kitchen Plates (拓扑或者暴力)
-
Online Courses In BSU CodeForces - 770C (拓扑)