hdu 5693
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=5693
等差数列当划分细了后只用比较2个或者3个数就可以了，因为大于3的数都可以由2和3组合成。
区间DP，用dp[i][j]表示在i到j之间可以删除的最大数，枚举区间长度，再考虑区间两端是否满足等差数列(这是考虑两个数的)，再i到j之间枚举k，分别判断左端点右端点和k是否构成等差数列(还是考虑两个数的)，判断左端点,k,右端点是否构成等差数列(这是考虑三个数的)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; const int M = + ; bool vis[M][M];
int dp[M][M],n,m,a[M];
int max(int x,int y){return x>y?x:y;} void solvedp()
{
for (int len= ; len<=n ; len++){
for (int l= ; l<=n ; l++){
int r=l+len;
if (r>n) break;
if (vis[l][r]&&dp[l+][r-]==r-l-)
dp[l][r]=max(dp[l][r],dp[l+][r-]+);
for (int i=l ; i<=r ; i++)
dp[l][r]=max(dp[l][r],dp[l][i]+dp[i+][r]);
for (int i=l+ ; i<r ; i++){
if (vis[l][i]&&dp[l+][i-]==i-l+)
dp[l][r]=max(dp[l][r],dp[l+][i-]+dp[i+][r]+);
if (vis[i][r]&&dp[i+][r-]==r-i-)
dp[l][r]=max(dp[l][r],dp[l][i-]+dp[i+][r-]+);
if (vis[l][i]&&vis[i][r]&&dp[l+][i-]==i-l-&&dp[i+][r-]==r-i-
&&a[r]-a[i]==a[i]-a[l])
dp[l][r]=max(dp[l][r],r-l+);
}
}
}
} int main()
{
int t;
scanf("%d",&t);
while (t--){
memset(vis,false,sizeof(vis));
memset(dp,,sizeof(dp));
scanf("%d%d",&n,&m);
for (int i= ; i<=n ; i++) scanf("%d",&a[i]);
for (int i= ; i<=m ; i++) {
int x;
scanf("%d",&x);
for (int i= ; i<=n ; i++)
for (int j=i+ ; j<=n ; j++)
if (a[j]-a[i]==x)
vis[i][j]=true;
}
solvedp();
printf("%d\n",dp[][n]);
} return ;
}
lightoj 1422
有n个party，姑娘参加每个party都必须穿规定好的种类的衣服，可以将多件不同种类的衣服都套在身上，只要最外面的一层衣服满足party的规定就行了，但是一旦脱下的衣服就不能再次穿上，问最少需要多少件衣服。
比如第二组样例 1 2 1 1 3 2 1 先穿上种类1的衣服参加晚会1 ，不脱然后继续穿上种类2的衣服参加晚会2，再脱下种类2衣服参加晚会3,4，然后再穿上种类3衣服参加晚会5，再脱下它穿上种类2衣服参加晚会6，在脱下它，此时身上只剩种类1衣服，刚好参加最后一个晚会，所以需要种类1 2 3 2 四件衣服。
乍一看就是当遇见之前没有遇见过的种类的衣服的时候，答案肯定要加一，当遇到了之前见过的种类的衣服，此时就要考虑是否穿上这件衣服也就是答案是否要加一，此时就一个用到二维区间dp，dp[i][j]表示在区间i到j之间需要的最少的衣服数，当穿 j 这件衣服的时候，dp[i][j]=dp[i][j-1]+1,不穿的时候那肯定是之前也遇见过这个种类的衣服还穿在身上，那么就在i到j之间枚举k，当a[k]==a[j]的时候此时的dp[i][j]=min(dp[i][j],dp[i][k],dp[k+1][j])
dp无非就是状态的转移，这里的就是穿不穿这件衣服这个状态，找出这两个选择后的状态发展。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; int min(int x,int y) {return x<y?x:y;}
const int M = + ;
int dp[M][M],a[M]; int main()
{
int t,ans=,n;
scanf("%d",&t);
while (t--){
scanf("%d",&n);
for (int i= ; i<=n ; i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++)
for(int j=i;j<=n;j++)
dp[i][j]=j-i+;
for (int i=n- ; i>= ; i--){
for (int j=i+ ; j<=n ; j++){
dp[i][j]=min(dp[i][j],dp[i][j-]+);
for (int k=i ; k<j ; k++){
if (a[j]==a[k])
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j-]);
}
}
}
printf("Case %d: %d\n",++ans,dp[][n]);
}
return ;
}