转自：http://www.cnblogs.com/qscqesze/p/5516294.html
分析：我写区间dp，都是拘泥于形式，随便更新（实在是太弱了）
但是其实我们如果思考清楚区间dp基于什么进行转移，转移就更加清晰
看了电子科技大学的巨巨的博客以后，豁然开朗，就是一个很简单的O(n^3)转移
我们要搞清楚他是根据什么进行转移
我发现在进行dp时，往往根据区间第一个元素的归属进行分类讨论转移
而这个题也是一样，我么依旧考虑第一个元素的归属，但是还有3个的情况
注意一下特判3个的就好了（注意判3个的时候，不需要n4枚举，只需要和最右边那个店组成3个就好，因为小的已经被枚举过），分类讨论就好了
#include <cstdio> #include <iostream> #include <ctime> #include <vector> #include <cmath> #include <map> #include <stack> #include <queue> #include <algorithm> #include <cstring> using namespace std; typedef long long LL; const int N=3e2+5; const int INF=0x3f3f3f3f; const int mod=1e9+7; bool mark[N][N]; int a[N],dp[N][N],n,m,T; int main(){ scanf("%d",&T); while(T--){ memset(mark,false,sizeof(mark)); memset(dp,0,sizeof(dp)); scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%d",&a[i]); for(int i=1;i<=m;++i){ int x;scanf("%d",&x); for(int j=1;j<n;++j) for(int k=j+1;k<=n;++k) if(a[k]-a[j]==x) mark[j][k]=true; } for(int len=1;len<=n;++len){ for(int l=1;l<=n;++l){ int r=l+len; if(r>n)break; if(mark[l][r]&&dp[l+1][r-1]==(r-l-1)) dp[l][r]=max(dp[l][r],dp[l+1][r-1]+2); for(int i=l;i<r;++i) dp[l][r]=max(dp[l][r],dp[l][i]+dp[i+1][r]); for(int i=l+1;i<r;++i){ if(mark[l][i]&&mark[i][r]&&a[i]-a[l]==a[r]-a[i]&&dp[l+1][i-1]==(i-1-l)&&dp[i+1][r-1]==(r-i-1)) dp[l][r]=max(dp[l][r],r-l+1); } } } printf("%d ",dp[1][n]); } return 0; }