字符串折叠 bzoj-1090 SCOI-2003
题目大意：我说不明白...链接
注释：自己看
想法：动态规划
状态：dp[i][j]表示从第i个字符到第j个字符折叠后的最短长度。
转移：dp[l][r]=min(r-l+1,dp[l][k]+dp[k+1][r])
当k+1~r可以有l~k得到时还要
dp[l][r]=min(dp[l][r]，dp[l][k]+2+calc((r-l+1)/(k-l+1)))；//calc用来计算一个十进制数所占位数
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char s[101];
int f[101][101];
bool mark[101][101];
bool jud(int l,int r,int cl,int cr)
{
if((r-l+1)%(cr-cl+1)!=0)return false;
for(int i=l;i<=r;i++)
if(s[i]!=s[(i-l)%(cr-cl+1)+cl])return false;
return true;
}
int get(int x)
{
int t=0;
while(x)
{
x/=10;t++;
}
return t;
}
int dp(int l,int r)
{
if(l==r)return 1;
if(mark[l][r])return f[l][r];
mark[l][r]=1;
int t=r-l+1;
for(int i=l;i<r;i++)
{
t=min(t,dp(l,i)+dp(i+1,r));
if(jud(i+1,r,l,i))
t=min(t,dp(l,i)+2+get((r-i)/(i-l+1)+1));
}
return f[l][r]=t;
}
int main()
{
scanf("%s",s);
printf("%d",dp(0,strlen(s)-1));
return 0;
}
小结：好题，就是那个十进制的太不要脸了.......