BZOJ2708 [Violet 1]木偶

嗯……刚看到题的时候各种贪心乱搞，结果不过，然后才发现是DP……

排个序，考虑一下最后答案的形式，一定是一段\这样一段/这样交替出现(额，这个斜杠说的是你把数从上到下排成两列，然后连的方法……），为啥这样优呢，因为这样就相当于有一边靠着边界了

那么我们f[i]表示前i个数的答案，枚举最后一段\或者/这样的长度，然后考虑计算这一段最多能扔掉多少个，因为之前一段的连法和他是反着的，所以可以认为他是靠着上边界的

枚举答案再判断就行了

其实只要这一段是固定的，不管是/这么连还是\这样连答案都是一样的

复杂度O(n^4)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<queue>
#include<stack>
using namespace std;
#define MAXN 60
#define MAXM 1010
#define INF 1000000000
#define MOD 1000000007
#define eps 1e-8
#define ll long long
int n,f[MAXN],a[MAXN];
int cal(int l,int r){
	int i,j;
	for(i=1;i<=r-l+1;i++){
		if(abs(a[l+i-1]-a[r-i+1])<=1){
			return i-1;
		}
		for(j=l+i;j<=r;j++){
			if(abs(a[j]-a[j-i])>1){
				return i-1;
			}
		}
	}
	return r-l+1;
}
int main(){
	int i,j;
	while(scanf("%d",&n)!=EOF){
		for(i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		sort(a+1,a+n+1);
		memset(f,0,sizeof(f));
		for(i=1;i<=n;i++){
			for(j=0;j<i;j++){
				f[i]=max(f[i],f[j]+cal(j+1,i));
			}
		}
		printf("%d\n",f[n]);
	}
	return 0;
}

/*

*/