首页 > 代码库 > uva1351 dp

uva1351 dp

2024-07-30 14:17:01   218人阅读

这题说的是给了 一个串 然后 比如 aaaaabbbbbbcdddd 可以化成5(a)6(b)c4(d) 这样的串明显 长度更短了 ， 请 计算出使得这个串最短的 长度是多少，

dp[i][j] 表示 从字符串i到j 之间的最短的 长度， 然后 先预处理出来 可以简化的 区间 

然后 枚举每个区间 去求得最小值

#include <iostream>#include <cstdio>#include <algorithm>#include <string.h>#include <vector>using namespace std;const int maxn =205;int dp[maxn][maxn];char str[maxn];void inti(int n){   for(int i=0; i<n; ++i)    for(int j=i; j<n; ++j)       dp[i][j]=j-i+1;}bool cmp(int s, int t, int num, int n){    for(int i=0; i<num; ++i)         if(str[s+i]!=str[t+i]||t+i>=n) return false;    return true;}int ccc(int v){   int ans=0;   while(v>0) {     ans++;     v/=10;   }   return ans;}int main(){     int cas;     scanf("%d",&cas);     for(int cc=1; cc<=cas; ++cc){          scanf("%s",str);          int n=strlen(str);          int ok=0;          inti(n);          for(int i=1; i<=n; ++i){              for(int j=0; j+i<n; j++){                   ok=0;                   for(int k=j+i; k<n; k+=i){                        if(cmp(j,k,i,n)==true) ok++;                        else break;                   }                   for(int k=0; k<i-1; ++k)                   dp[j][j+i-1]=min( dp[j][k+j] + dp[k+j+1][j+i-1] , dp[j][j+i-1] );                   dp[j][j+i*(ok+1)-1] =min( dp[j][j+i*(ok+1)-1],dp[j][j+i-1]*(ok+1));                   dp[j][j+i*(ok+1)-1] =min(dp[j][j+i*(ok+1) -1 ] ,dp[j][j+i-1]+2+ccc(ok+1) );              }          }          for(int i=1; i<=n; ++i){              for(int j=0; j+i-1<n; ++j)                 for(int k=0; k<i-1; ++k)                   dp[j][j+i-1]=min(dp[j][j+i-1],dp[j][j+k]+dp[j+k+1][i+j-1]);          }          printf("%d\n",dp[0][n-1]);     }    return 0;}
View Code

 

uva1351 dp


联系
我们