嗯……刚看到题的时候各种贪心乱搞，结果不过，然后才发现是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; } /* */
