NYOJ 1067 Compress String(区间dp)
生活随笔
收集整理的這篇文章主要介紹了
NYOJ 1067 Compress String(区间dp)
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
Compress String
時(shí)間限制:2000?ms ?|? 內(nèi)存限制:65535?KB 難度:3 描述Each test case contains a string, the length of the string is no more than 200, all the character is lower case alphabet.
題意:給出一個(gè)長(zhǎng)度不超過200的字符串,把這個(gè)字符串按照一定規(guī)則壓縮,即可以把幾個(gè)連續(xù)的相同子串壓縮成一個(gè)串,例如可以把letsgogogo壓縮為lets3(go),壓縮后的子串如果還可以繼續(xù)壓縮,則可以繼續(xù)壓縮,如可以將nowletsgogogoletsgogogoandrunrunrun壓縮為now2(lets3(go))and3(run)。問經(jīng)過壓縮后這個(gè)字符串的最短長(zhǎng)度是多少。
分析:?區(qū)間DP,dp[i][j]表示從i到j(luò)的字符串表示的最短長(zhǎng)度。
? ? ? ? ? dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])。? ? ? ? ? 然后去判斷當(dāng)前子串能不能壓縮,即是否由重復(fù)字符串組成,判斷時(shí)只需暴力枚舉重復(fù)長(zhǎng)度,去判斷即可。
? ? ? ? ? 如果當(dāng)前子串可以壓縮,則dp[i][j] = min(dp[i][j], dp[i][i + len - 1] + 2 + digcount((j - i + 1) / len));,
? ? ? ? ? 注意如果是數(shù)字,要用數(shù)字的位數(shù)表示增加的個(gè)數(shù),而不是單純的增加1.
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 210; #define INF 0x3fffffff char str[N]; int n, dp[N][N];int digit_cnt(int x) {int a = 0;while(x) {a++;x /= 10;}return a; }bool check(int l, int r, int len) {if((r - l + 1) % len) return false;for(int i = l; i < l + len; i++) {for(int j = i + len; j <= r; j += len)if(str[i] != str[j]) return false;}return true; }int get_ans() {int i, j, k;n = strlen(str+1);for(i = 1; i <= n; i++) dp[i][i] = 1;for(i = n - 1; i >= 1; i--) {for(j = i + 1; j <= n; j++) {dp[i][j] = INF;for(k = i; k < j; k++)dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);for(int len = 1; len <= j-i+1; len++) {if(check(i, j, len)) {dp[i][j] = min(dp[i][j], dp[i][i+len-1] + 2 + digit_cnt((j - i + 1) / len));}}}}return dp[1][n]; }int main() {while(~scanf("%s", str+1)) {printf("%d\n", get_ans());}return 0; }總結(jié)
以上是生活随笔為你收集整理的NYOJ 1067 Compress String(区间dp)的全部?jī)?nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 撸完这些JVM知识点,明天就去面试阿里P
- 下一篇: 一次蚂蚁金服的辛酸面试历程