首页 > > 程序设计 > C/C++ >

Folding UVA - 1630

2018-06-17 22:05:12来源：未知阅读 ()

题目

ans[i][j]表示由原串第i个字符到第j个字符组成的子串的最短折叠长度
如果从i到j本身可以折叠，长度就是本身长度或折叠后的长度的最小值
***此处参考：http://blog.csdn.net/a197p/article/details/48701227
（自己只能想到去掉左边或右边字母，这样难以转移状态）
如果不能，就是将其分成两个子串后子串连接起来长度的最小值（如果比本身长度还大则取本身）
如果能折叠的显然一定是折叠比分成两段好，当然如果不确定可以折叠、不折叠都试一下，然后取长度最小值

 1 #include<iostream>
 2 #include<cstring>
 3 #include<string>
 4 using namespace std;
 5 string str;
 6 int ans[110][110];
 7 string ans2[110][110];
 8 void dp(int l,int r)
 9 {
10     if(r==l)//由于下面写的是i=1,i<len, 可以在只有1个字符时特判
11     {
12         ans[l][l]=1;
13         ans2[l][l]=str[l];
14         return;
15     }
16     bool flag,flag2=false;
17     int len=r-l+1,i,j;
18     string temp,temp2;
19     ans2[l][r]=str.substr(l,r-l+1);
20     for(i=1;i<len;i++)//枚举每段i字符，循环暴力求是否是可以折叠的
21         if(len%i==0)//如果每段i字符可以分成整数段
22         {
23             flag=false;
24             temp=str.substr(l,i);//记录下第一段 
25             for(j=i;j<len;j+=i)
26                 if(temp!=str.substr(l+j,i))//如果分出来的某一段跟第一段不符，就是不能折叠
27                 {
28                     flag=true;
29                     break;
30                 }
31             if(flag==false)//如果分出来的所有段都跟第一段相同，就是能折叠
32             {
33                 flag2=true;
34                 if(ans[l][l+i-1]==0x3f3f3f3f)//曾经忘了，导致无法过UUUUUUUGLUUUUUUUGLZ
35                     dp(l,l+i-1);//如果是折叠，只需更新第一段的最小长度
36                 //temp2=len/i+48;//这样错的，超过9的数字就不行了
37                 char c[20];//存储折叠的次数转换成的字符串 
38                 sprintf(c,"%d",len/i);
39                 temp2=c;
40                 temp2+='('+ans2[l][l+i-1]+')';
41                 //temp2的构成是折叠的次数(就是c)+'('+最短的第一段+')'
42 //直接写temp2=c+...会出奇怪的问题，可能跟参与运算的类型太混乱(string,char,char*)有关系
43                 if(ans2[l][r].length()>temp2.length())//如果折叠完比原串短或者比之前找到的某种折叠方法短就更新
44                     ans2[l][r]=temp2;
45             }
46         }
47     if(flag2==true)//如果能折叠的显然一定折叠比分成左右两段好
48     {
49         ans[l][r]=ans2[l][r].length();
50     }
51     else
52     {
53         for(i=l;i<r;i++)//分成l~i和(i+1)~r两段，显然i可以为l~(r-1)
54         {
55             if(ans[l][i]==0x3f3f3f3f)
56                 dp(l,i);
57             if(ans[i+1][r]==0x3f3f3f3f)
58                 dp(i+1,r);
59             if(ans[l][i]+ans[i+1][r]<ans[l][r])
60             {
61                 ans[l][r]=ans[l][i]+ans[i+1][r];
62                 ans2[l][r]=ans2[l][i]+ans2[i+1][r];
63             }
64         }
65     }
66 }
67 int main()
68 {
69     while(cin>>str)
70     {
71         memset(ans,0x3f,sizeof(ans));
72         dp(0,str.length()-1);
73         cout<<ans2[0][str.length()-1]<<'\n';
74     }
75     return 0;
76 }