Sdut 1309不老伝説(区間dp)

タイトル:
たくさんの石を与えて、輪に囲まれています.石を所定の色に染めることが要求されているが、毎回最大k個の石しか染めることができず、最大c種の色を使うことが制限されている.
問題:
この問題とhdu 2476はスープを交換しても薬を交換しない.何と言いますか.
まず杭電のあの問題(どのように空から目標列に変わるかを考える限り)を考えて、色を制限しないで、言いやすい.では状態dp[i][j]はiからjまで目標列にブラシをかける最小ステップ数を表し、iからjまでの区間についてi+1からjがブラシをかけ終わったと仮定し、それでは長い間iを単独でブラシするという点で、dp[i][j]=dp[i+1][j]+1;次に、ブレークポイント更新を列挙し、区間内のあるポイントとブレークポイントiが等しい場合、dp[i+1][k]+dp[k+1][j]の2つのセグメントに分けて行を変更できることを説明する.
なぜi+1なのか.i位置の列がk位置の列に等しいと考えると、i点ブラシk点もブラシに違いないが、i点が1つ少なくなってもdp[i+1][k]だけで同じではないか.yes!i点k点がなければ必ずブラシをかけるので、決定の答えはaと表記されているので、今i点を加えると必ずブラシがかかるので、i点とk点が同時にブラシされるので、決定の答えは変わらないはずだ.そこでdp[i][j]=max(dp[i+1][k]+dp[k+1][j])という方程式が出てくる.
よし!今から本題に戻って、古い伝説がどうするのか、この問題は色の多少を制限しているので、私はこの色の制限が看板だと丁寧に言うことができます.どうしてですか.
このように考えて、もし目標の石が5中の色があるならば、私は今あなたに3中の色を使うことを限定して、どのようにブラシしても成功することができないことを考えて、3中の色はまったく5中の色にならないためです!実はこの問題に制限された色は役に立たない.目標を達成するには、色が目標が持っている色に等しいに違いないからだ.色の問題が解決しました!
では今問題が来ました!k個の石の制限はどうしますか!ほほほ、これはずっと簡単で、状態が移るたびにサブ区間が個数がk以下であるかどうかを判断すればいいです!
では問題解決!

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
typedef long long lld;
#define oo 0x3f3f3f3f
#define mod 1000000007
#define maxn 400+5
int dp[maxn][maxn];
int a[maxn];

int main()
{
    int n,C,K,ans,t;
    while(scanf("%d %d %d",&n,&C,&K)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            a[i+n]=a[i];
        }
        for(int i=1;i<=2*n;i++)
            for(int j=i+1;j<=2*n;j++)
                dp[i][j]=oo;
        for(int i=1;i<=2*n;i++)
            dp[i][i]=1;
        for(int L=2;L<=n;L++)
        {
            for(int i=1;i+L-1<2*n;i++)
            {
                int j=i+L-1;
                if(j-i+1<=K)
                    dp[i][j]=dp[i+1][j]+1;
                t=min(i+K-1,j);
                for(int k=i+1;k<=t;k++)
                    if(a[i]==a[k])
                        dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
            }
        }
        ans=oo;
        for(int i=1;i<=n;i++)
            ans=min(ans,dp[i][i+n-1]);
        printf("%d
",ans);
    }
	return 0;
}
/*
4 3
0 0
0 4
4 0
1 1

4 10
0 0
0 4
4 4
4 0
*/