BZOJ2708: [Violet 1]木偶 贪心+dp

题解:

其实很有一些玄学,不知道怎么想到是一个dp问题的。

首先肯定要将数组排序,然后令$f[i]$表示前$i$对中至多扔掉几个。

那就有转移方程$f[i]=\sum_{j=0}^{i-1}max\{f[j]+calc(j+1,i)\}$。

$calc(x,y)$表示从第$x$个到第$y$个至多扔掉几个。

我们可以考虑枚举答案判断是否合法。

我们考虑能否扔掉$k$个。

满足条件当且仅当存在k对两两之间均不能匹配且剩下的存在一种完备匹配。

我们贪心的来分配去达成这个条件。

怎么贪心呢。。。

对于均不能匹配，我们令第$i$小的去匹配第$i$大的.

于是就做完了这道题目。

但是为什么这样分段是对的呢...我觉得大概就是因为有匹配范围是-1,0,1这个条件吧。

我觉得大概不是很容易证明，但是经过了对拍的考验就能出了吧。

嗯，我是这样想的。

代码:

#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 51
int a[N],f[N];
inline int dis(int a,int b){
	return a>b?a-b:b-a;
}
inline int cal(int x,int y){
	for(int j=1;j<=y-x+1;++j){
		for(int i=x;i+j<=y;++i)
			if(dis(a[i],a[i+j])>1)
				return j-1;
		if(dis(a[x+j-1],a[y-j+1])<=1)
			return j-1;
	}
	return y-x+1;
}
int main(){
#ifndef ONLINE_JUDGE
	freopen("tt.in","r",stdin);
#endif
	int n,i,j,k;
	while(scanf("%d",&n)!=EOF){
		for(i=1;i<=n;++i)
			scanf("%d",&a[i]);
		for(sort(a+1,a+n+1),i=1;i<=n;++i)
			for(f[i]=j=0;j<i;++j)
				f[i]=max(f[i],f[j]+cal(j+1,i));
		cout<<f[n]<<endl;
	}
	return 0;
}