小小粉刷匠_牛客博客

来源：牛客网：

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

"lalala,我是一个快乐的粉刷匠",小名一边快活地唱着歌,一边开心地刷着墙",兴致突然被打断,"小名,你今天如果刷不完这一栋楼的墙，那么你就等着被炒鱿鱼吧",老板声嘶力竭的吼着。苦恼的小名因为不想被炒鱿鱼,所以希望尽量快地刷完墙,由于他本人的数学基础很差,他现在请你来帮助他计算最少完成每一堵墙需要刷多少次。每一面墙有n个段,对于每个段指定一个目标颜色ci。刚开始的时候所有的墙壁为白色,我们现在有一个刷子,刷子长度为k,刷子每次可以选择一种颜色,然后选择段数为(1～k)连续的墙段刷成选择的一种颜色。我们现在想要知道，为了把墙变成目标颜色，最少刷多少次(保证指定的目标颜色一定不为白色)。

输入描述:

对于每一个案例,我们第一行包括两个整数n,k(1<=n<=100,1<=k<=50,k<n),表示墙的长度为n,刷子的长度为k。第二行输入n个整数(c1c2...cn),(1<=ci<=256),表示对于墙的每一段指定的颜色。

输出描述:

输出一个数,表示小名最少刷多少次。

示例1
输入
复制

3 3
1 2 1

输出
复制

示例2
输入
复制

5 4
5 4 3 3 4

输出
复制

题解：

区间dp
首先上一个区间dp的模板

/*
dp[i][j]是从1到n
初始化dp[i][i]=1,或者其他的
*/
for(int len=2; len<=n; len++){//枚举长度
        for(int i=1; i<=n; i++){//枚举起点i
            int j=i+len-1;//枚举终点j
            if(j > n) break;
            for(int k=i; k<j; k++){//找断点k的位置,可随实际情况修改
            //将区间[i,j],拆成[i,k][k+1,j]
                ......
            }
        }
    }

dp[i][j]表示第i个位置到第j个位置所需要最小步数
dp[i][i]初始化为1,dp[i][j]=dp[i+1][j]+1
题目是有限制ank，每次画的长度为k
第一种情况：
ank>len,（len为我们当前枚举的长度），我们可以直接画完，我们在枚举断点k时，先判断a[i]==a[k]，如果相等有
dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j])，最少操作次数就是讲第i个与第k个一起涂，所以区间[i,j]中做端点i就不用考虑了
第二种：
当len>ank时，我们的刷子长度不够，所以直接将区间拆分即可
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])
区间dp多为此套路

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=140;
int dp[maxn][maxn];
int a[maxn];
int main()
{
    int n,ank;
    cin>>n>>ank;
    for(int i=1;i<=n;i++)
    {
            cin>>a[i];
            dp[i][i]=1;
    }

    for(int len=2;len<=n;len++)
    {
            for(int i=1;i<=n;i++)
        {
            int j=i+len-1;
            dp[i][j]=dp[i+1][j]+1;
            if(j>n)break;
            if(ank>=len)
                for(int k=i+1;k<=j;k++)
                {
                    if(a[i]==a[k])dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
                }
            else 
            for(int k=i+1;k<=j;k++)
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);

        }

    }
    printf("%d\n",dp[1][n]);
    return 0;
}