首页 > 代码库 > bzoj1068题解

bzoj1068题解

2024-09-15 03:44:42   214人阅读

【解题思路】

　　区间DP。f[l][r][s]表示l到r的子串能最小被压成的长度，其中s∈[0,1]表示该串压缩后串中是否能含有M。

　　我们可以通过三种方式转移：

•如果该区间含有缓冲区，则其可分成两个可能带有M的区间，中间插一个M，这样转移方程即：f[l][r][1]=min{f[l][mid][1]+1+f[mid+1][r][1]}(l≤mid<r)；

•只压缩左边的区间，不压缩右边的区间，这样转移方程即：f[l][r][s]=min{f[l][mid][s]+r-mid}(l≤mid<r)；

•如果这个区间可被二等分，则其可分成不含M的左区间和一个R，这样转移方程即为：f[l][r][s]=min{f[l][(l+r)/2][0]+1}；

　　时间复杂度O(n3)。

【参考代码】

技术分享
 1 #include <bits/stdc++.h> 2 #define range(i,c,o) for(register int i=(c);i<(o);++i) 3 #define dange(i,c,o) for(register int i=(c);i>(o);--i) 4 using namespace std; 5   6 char str[55]; 7 int f[55][55][2]; 8 int main() 9 {10     scanf("%s",str); int n=strlen(str);11     range(len,1,n+1) range(lef,0,n-len+1)12     {13         int rig=lef+len-1;14         f[lef][rig][0]=f[lef][rig][1]=len;15         range(mid,lef,rig)16         {17             range(S,0,2)18             f[lef][rig][S]=min(19                 f[lef][rig][S],20                 f[lef][mid][S]+rig-mid21             );22             f[lef][rig][1]=min(23                 f[lef][rig][1],24                 f[lef][mid][1]+f[mid+1][rig][1]+125             );26         }27         int L=rig-lef+1;28         if(~L&1)29         {30             L>>=1; bool flag=0;31             range(i,0,L)32             {33                 if(flag=str[i+lef]!=str[i+lef+L])34                 {35                     break;36                 }37             }38             if(!flag) range(S,0,2)39             f[lef][rig][S]=min(40                 f[lef][rig][S],41                 f[lef][lef+L-1][0]+142             );43         }44     }45     return printf("%d\n",f[0][n-1][1]),0;46 }
View Code

 

bzoj1068题解


联系
我们