BZOJ1260: [CQOI2007]涂色paint【记忆化DP】

dzy posted @ 2013年6月07日 15:32 in BZOJ with tags BZOJ 记忆化DP , 2106 阅读

类似记忆化dp、、

f[i][j]表示i~j这一段最少要涂几次。每次递归计算、头尾如果相同可以最先涂、所以可以减1、然后合并上来就行、、

最近写的代码怎么都这么短?还是我太弱了只会刷水?唉、、囧、、、

#include<cstdio>
#include<algorithm>
#include<cstring>
const int inf=1000000009;
int F[60][60]={0},l;    char s[60];
int f(int l,int r){
    if(l==r)    return 1;   if(F[l][r]) return F[l][r]; F[l][r]=inf;
    for(int i=l;i<=r;i++)   F[l][r]=std::min(f(l,r),f(l,i)+f(i+1,r));
    return F[l][r]-=(s[l]==s[r]);
}int main(){
    scanf("%s",s);  l=strlen(s);    printf("%d\n",f(0,l-1));   return 0;
} 

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter