区间dp

没有好好地做过区间dp

今天算是正式地初体验
没想出来，但是有点感觉
先暂时不说dp地推导

我直接说怎么做地吧
直接设dp[i][j]表示区间(i,j)的最小需要的衣服数量
然后直接枚举长度，之后枚举断点，dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k][j])
判断条件:c[i]==c[k]
感觉好奇妙哇

形式如此的固定，正式比赛时我们是不是可以根据推导出的少量信息蒙呢？

接下来说明转移公式真正的推导：
我们要求dp[i][j]
首先我们知道若i->j所有的c都不一样那么一定是j-i+1
接下来我们想想，对于c[i]如果i+1->j都没有c[i]的话
那么c[i]此时选的衣服一生都不会再次被重复运用了
那么dp[i][j]=dp[i+1][j]+1

如果有的话，这就是我们所说的断点了，其实也就是枚举，我们枚举衣服c[i]被重复利用的点
若c[i]==c[k]
则dp[i][j]=min(dp[i+1][k-1]+dp[k][j],dp[i][j])
意为重复利用。

#include<iostream>
#include<algorithm>
using namespace std;
int c[110];
int dp[110][110];
int n;
int main(){
    int T;scanf("%d",&T);
    for (int tcase=1;tcase<=T;++tcase){
        scanf("%d",&n);
        for (int i=1;i<=n;++i)scanf("%d",&c[i]);
        for (int i=1;i<=n;++i)dp[i][i]=1;
        for (int i=1;i<n;++i){
            if (c[i]==c[i+1])dp[i][i+1]=1;
            else dp[i][i+1]=2;
        }
        for (int len = 2;len<=n;++len){
            for (int i=1,j=i+len-1;j<=n;++i,++j){
                dp[i][j] = dp[i+1][j]+1;
                for (int k=i+1;k<=j;++k){
                    if (c[i]==c[k]){
                        dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k][j]);
                    }
                }
            }
        }
        printf("Case %d: %d\n",tcase,dp[1][n]);
    }
}