LightOJ - 1422 （區間DP）

題意：有t組數據，對于每組，有n個聚會需要參加，下面依次是參加各個聚會需要的衣服編號，要求所需要的衣服一定穿在外面，在操作的時候，可以選擇穿上一件衣服或脫下一件衣服，脫下的衣服不能繼續使用，問最少需要的衣服數量。

分析：在穿第j件衣服的時候，我們需要知道原先的狀態是否穿著第j件衣服，所以我們需要枚舉所有間斷的區間，需要用到區間dp

? ? ? ? ? dp[i][j]代表,從第i個聚會到第j個聚會需要的最少的衣服數量

? ? ? ? ? dp[i][j]最壞情況是第j件衣服是新穿的，dp[i][j]=dp[i][j-1]+1;

? ? ? ? ? 然后依次枚舉k,如果第k件衣服和j件衣服相同

? ? ? ? ? 那么 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j-1])? （dp[i][k]保證最后一定有第k件衣服給第j次)

代碼如下：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
int dp[110][110];
int a[110];
int t,n,Case=0;
int main()
{scanf("%d",&t);while(t--){Case++;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i==j)dp[i][j]=1;else if(i>j)dp[i][j]=0;else dp[i][j]=INF;}for(int l=1;l<=n-1;l++)for(int i=1;i<=n-l;i++){int  j=l+i;dp[i][j]=dp[i][j-1]+1;for(int k=i;k<j;k++){if(a[j]==a[k])dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j-1]);}}printf("Case %d: %d\n",Case,dp[1][n]);}return 0;
}

?