CQOI2007 涂色 paint (区间dp)

听说这道题是当年省选题

于是兴致勃勃拿来做了做

至于如何想到思路...

事实上没想象中那么简单...

脑阔挺疼的...

(一开始都没看出来是区间dp)

想到可以区间dp，然后就似乎没啥大问题

枚举区间dp[i][j]的时候，如果i j一样那就好说，相当于当初某一次涂的时候多往外涂一格就好

如果i j不一样？我反而在这里懵了

但我误打误撞就给正解写出来了

想不到正解居然这么简单？？？

认真思考之后大体明白了

因为不能像i==j那样直接多涂一个

所以就可以直接区间枚举了...

总有一个是最优的

 1 #include<cstdio>
 2 int min(int a,int b){return a<b?a:b;}
 3 char colin[52];
 4 int col[52],dp[52][52];
 5 int main()
 6 {
 7     scanf("%s",colin);
 8     int n=strlen(colin);
 9     for(int i=0;i<n;i++)
10     {
11         col[i+1]=colin[i];
12     }
13     memset(dp,0x3f,sizeof(dp));
14     for(int i=0;i<=n+1;i++)dp[i][i]=1;
15     for(int d=1;d<n;d++)
16     {
17         for(int i=1;i+d<=n;i++)
18         {
19             if(col[i]==col[i+d])dp[i][i+d]=min(dp[i][i+d-1],dp[i+1][i+d]);
20             else for(int k=i;k<i+d;k++)
21             {
22                 dp[i][i+d]=min(dp[i][i+d],dp[i][k]+dp[k+1][i+d]);
23             }
24         }
25     }
26     printf("%d",dp[1][n]);
27     return 0;
28 }

做完这道题之后你可以再去看看

[hdu2476]String painter(区间dp)

没错他们完全一样