首先想到的是贪心。。。肯定不对嘛。。。T T
然后发现其实是可以DP的。。。不过我们要先排序
令f[i]表示前i个木偶最坏要丢掉几个，则
f[i] = max(f[j] + calc(j + 1, i)) 其中 j < i
而calc(x, y)函数计算从第x个到第y个木偶匹配最多可以丢掉几个，方法是：
hzwer："枚举可以扔掉的数量k，判断剩下的能否相互匹配，不能返回k-1
以及被扔掉的能否相互匹配，能匹配返回k-1"
/**************************************************************
Problem: 2708
User: rausen
Language: C++
Result: Accepted
Time:24 ms
Memory:804 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
const int N = ;
int n, a[N], f[N]; inline int read(){
int x = , sgn = ;
char ch = getchar();
while (ch < '' || ch > ''){
if (ch == '-') sgn = -;
ch = getchar();
}
while (ch >= '' && ch <= ''){
x = x * + ch - '';
ch = getchar();
}
return sgn * x;
} int calc(int x, int y){
int i, k;
for (k = ; k <= y - x + ; ++k){
for (i = k; i <= y - x; ++i)
if (abs(a[i + x] - a[i + x - k]) > ) return k - ;
if (abs(a[x + k - ] - a[y - k + ]) <= ) return k - ;
}
return y - x + ;
} int main(){
int i, j;
while (scanf("%d", &n) != EOF){
for (i = ; i <= n; ++i)
scanf("%d", a + i);
sort(a + , a + n + );
memset(f, , sizeof(f));
for (i = ; i <= n; ++i)
for (j = ; j < i; ++j)
f[i] = max(f[i], f[j] + calc(j + , i));
printf("%d\n", f[n]);
}
return ;
}