Halloween Costumes
LightOJ - 1422
算法分析：
题意：
有N个宴会，对于每一个宴会都有对应的一种礼服，一个人都要穿一种礼服，脱了的不能再用，需要新买一件，礼服可以套着穿，参加宴会必须按顺序来，从第一个到第N个，问参加这些宴会最少需要几件礼服。
分析：
要不是老师给的区间DP，还真不知道从区间DP下手，但好像这种选择有影响到后面的状态，好像一般都用区间DP。
好，我们知道是区间DP了，dp[i][j]自然表示从i到j至少穿的衣服数量，我们如何优化呢，
我们先假设选择a[j]衣服，我们什么时候不用选择a[j]衣服呢，那就是断点k，如果有a[k]==a[j],那我们就不用选了，就需要重新比较了，得到状态转移方程，dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j-1])，注意到j-1，不选择a[j]这件衣服;
阶段：区间长度
状态：枚举区间左端点
决策：间断点k
状态转移方程：
dp[i][j]=dp[i][j-1]+1;
if(a[j]==a[k]) //k有同一件
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j-1]);
边界条件：dp[i][i]=1;
看网上还有更简单的答案，倒着枚举，两重循环即可，不过已经很开心，第一次区间DP可以做出了。
代码实现：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int dp[1000][1000],a[1000];
int main()
{int t;cin>>t; int q=0;while(t--){q++;int n;cin>>n;for(int i=1;i<=n;i++)scanf("%d",&a[i]);memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){dp[i][i]=1;}for(int len=1;len<=n;len++) //区间长度for(int i=1;i<=n;i++) //枚举起点{int j=i+len-1; //区间终点dp[i][j]=dp[i][j-1]+1;if(j>n) break; //越界结束for(int k=i;k<j;k++) //枚举分割点，构造状态转移方程{if(a[j]==a[k]) //k有同一件dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j-1]); }}printf("Case %d: %d\n",q, dp[1][n]);}
}第二种方法：
另一种做法，很巧妙的简化成二重循环，但基本思想一样
/** Light OJ 1422 - Halloween Costumes* http://lightoj.com/volume_showproblem.php?problem=1422* 区间DP的思想。* 比如要求解i到j，dp[i][j].* 就是考虑i的衣服，一种是i的衣服只有在i使用，那么就是dp[i+1][j]+1件* 然后再i+1~j中枚举k，如果a[i]==a[k].那么dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k][j])* 注意因为i的衣服是可以使用多次的，所以不需要加1，是dp[k][j]* 思想很妙*/#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAXN=110;
int a[MAXN];
int dp[MAXN][MAXN];int main()
{int T;int n;scanf("%d",&T);int iCase=0;while(T--){iCase++;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)dp[i][j]=j-i+1;for(int i=n-1;i>=1;i--)//注意DP的顺序for(int j=i+1;j<=n;j++){dp[i][j]=dp[i][j - 1]+1;//这个表示第i个的衣服在后面没有利用了for(int k=i;k<=j - 1;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",iCase,dp[1][n]);}return 0;
}
//3.16重做
#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<map>
using namespace std;
using namespace std;
int a[10005],dp[10005][105];
int f(int t,int mod)
{while(t<0) t+=mod;return t%mod;
}
int main()
{int n,k;int t;scanf("%d",&t);int cas=0;while(t--){memset(dp,0,sizeof(dp));scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);dp[i][i]=1;}for(int len=2;len<=n;len++){for(int l=1;l<=n-len+1;l++){int r=l+len-1;dp[l][r]=dp[l][r-1]+1;for(int k=l;k<r;k++){if(a[r]==a[k])dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]-1);}}}printf("Case %d: %d\n",++cas, dp[1][n]);}return 0;
}