刷油漆 | FFY's Blog

题意

cxm 需要给一块长木板刷上油漆。他一次可以将一段的木板刷上同一种颜色，刷过的木板可以再刷成其他颜色。现在木板被分成了若干块，每块需要涂成一个确定的颜色。 cxm 希望你告诉他最少需要涂几次就可以将每块都涂成需要的颜色。

• 区间DP
• $turn$函数比较迷
• 有十分有毒~(学长有毒)~

还是比较简单的区间DP,就是在区间DP基础上加了一个$turn$
虽然我没搞懂$turn$(但我拿了90,滑稽)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2010;
int n,t,s[maxn];
int f[maxn][maxn];
int turn(int a,int b,int c)
{
    if(s[a]==s[b]||s[a]==s[c+1]||s[c]==s[b]||s[c]==s[c+1])return -1;
    return 0;
}
int main()
{
    freopen("paint.in","r",stdin);
    freopen("paint.out","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        memset(f,0x3f,sizeof f);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
             scanf("%d",&s[i]);
             f[i][i]=1;
        }
        for(int l=1;l<=n;l++)for(int i=1;i+l<=n;i++)
        {
             int j=i+l;for(int k=i;k<j;k++)
             f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+turn(i,j,k));
        }
        printf("%d\n",f[1][n]);
    }
}