本文共 1916 字，大约阅读时间需要 6 分钟。

1、

2、题目大意：

题目描述

输入

输出

示例输入

5 2 31 2 1 2 1

示例输出

3

提示

3、分析：

要求的是怎么通过刷颜色，使得形成最终的序列，我们已经知道可以给连续的不超过k块石头一次性涂色，求经过最少的次数使得空白序列形成给定的序列

此题跟hdu 2476有些类似，但是这道题目中的石头是围成的圈形的，也就是说12345是连续的，23451也是连续的，所以我们可以将数组开大一倍，令a[i+n]=a[i],就能实现循环的问题，我们设dp[i][j]为i-j区间内转换成给定序列的最小步数，那么先假设i位置是要涂色的dp[i][j]=dp[i+1][j],如果发现在这个区间内有a[k]==a[i]，说明i,k位置相同，如果i-k区间在给定一次刷的最大区间内，那么我们就可以一次刷好，dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j])

4、AC代码：

#include
   
    #include
    
     using namespace std;#define N 500#define INF 0x7fffffffint a[N];int dp[N][N];int main(){    int n,c,K;    scanf("%d%d%d",&n,&c,&K);    for(int i=1;i<=n;i++)    {        scanf("%d",&a[i]);        a[n+i]=a[i];//因为石头的位置是圈形的    }    for(int i=1;i<=2*n;i++)    {        for(int j=i;j<=2*n;j++)        dp[i][j]=j-i+1;    }    for(int j=1;j<=2*n;j++)    {        for(int i=j-1;i>=1;i--)        {            dp[i][j]=dp[i+1][j]+1;            for(int k=i+1;k<=j;k++)            {                if(a[i]==a[k] && k-i+1<=K)//如果i和k相同，那么可以只上一次色就行                dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);            }        }    }    int ans=INF;    for(int i=1;i<=n;i++)    {        ans=min(ans,dp[i][i+n-1]);    }    printf("%d\n",ans);    return 0;}
    
   

转载地址：http://hgddi.baihongyu.com/