CF607B

标签：ch const int 涂色 CF607B dp define

Zuma - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

跟 P4170 [CQOI2007]涂色 很像。

令DP[i][j]为消灭区间(i~j)所需要的最少次数。

考虑dp[i][j]的转移:

如果a[i]==a[j],则有dp[i][j]=dp[i+1][j-1]因为最后区间[i+1~j-1]被削的只有一个回文串，a[i],a[j]加入这个回文串之中被一起削掉(这就是跟 P4170 [CQOI2007]涂色 很像的地方，但又不同，也是本题的关键挺妙的一点)

其他正常转移即可

 初始化： 对于长度为1，有dp[i][i]=1; 但对于 [1,1] [2,2]这样长度为2的偶数字符串是dp转移不过来的，所以需要人工手动转换。（也是本题的重点） Code：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   
#define popb pop_back  
#define fi first
#define se second
const int N=510;
//const int M=;
const int inf=0x3f3f3f3f;     
//const ll INF=0x3ffffffffffff;
int T,n,a[N],dp[N][N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=n;j++) dp[i][j]=inf;
    for(int i=1;i<=n;i++) dp[i][i]=1;
    for(int i=1;i<n;i++) dp[i][i+1]=1+(a[i]!=a[i+1]);
    for(int len=3;len<=n;len++)
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            if(a[i]==a[j]) dp[i][j]=dp[i+1][j-1];
            for(int k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
        }
    printf("%d",dp[1][n]);
    return 0;
}

 

标签：ch,const,int,涂色,CF607B,dp,define
From： https://www.cnblogs.com/Willette/p/17181408.html