学步园

dp[l][r]:l -> r的最小值
1.r-l+1<=k，可以一次涂完
若a[l]==a[r]，那么必定先涂满
dp[l][r]=dp[l][r-1](a[l]==a[r])
否则分段处理
2.r-l+1>k，分段处理

分段：

对于区间[l,r]

考虑点l应该怎么染色

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive
************************************************/
/////////////////////////////////////////////////
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
/////////////////////////////////////////////////
const int inf=0x3f3f3f3f;
int n,c,k;
int a[410];

int dp[410][410];
/////////////////////////////////////////////////
int DP(int l,int r)
{
    if(dp[l][r]!=-1) return dp[l][r];
    if(l>=r) return dp[l][r]=1;
    if(r-l+1<=k && a[l]==a[r]) return dp[l][r]=DP(l,r-1);
    int ans=inf;
    rep(i,l,min(l+k-1,r)) if(a[l]==a[i])
    {
        ans=min(ans,DP(l,i-1)+DP(i+1,r));
    }
    return dp[l][r]=ans;
}
/////////////////////////////////////////////////
void input()
{
    scanf("%d%d%d",&n,&c,&k);
    rep(i,1,n) scanf("%d",&a[i]),a[n+i]=a[i];
}
void solve()
{
    ///////////////////init///////////////////
    int ans=inf;
    MS(dp,-1);
    ////////////////calculate////////////////
    
    /////////////////output/////////////////
    rep(i,1,n-1) ans=min(ans,DP(i,i+n-1));
    printf("%d\n",ans);
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("spring.in","r",stdin); freopen("spring.out","w",stdout);
    #endif
    input();
    solve();
    #ifdef _TEST
    for(;;);
    #endif
    return 0;
}