首先想到的是贪心。。。肯定不对嘛。。。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"
1 /************************************************************** 2 Problem: 2708 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:24 ms 7 Memory:804 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13 14 using namespace std; 15 const int N = 55; 16 int n, a[N], f[N]; 17 18 inline int read(){ 19 int x = 0, sgn = 1; 20 char ch = getchar(); 21 while (ch < '0' || ch > '9'){ 22 if (ch == '-') sgn = -1; 23 ch = getchar(); 24 } 25 while (ch >= '0' && ch <= '9'){ 26 x = x * 10 + ch - '0'; 27 ch = getchar(); 28 } 29 return sgn * x; 30 } 31 32 int calc(int x, int y){ 33 int i, k; 34 for (k = 1; k <= y - x + 1; ++k){ 35 for (i = k; i <= y - x; ++i) 36 if (abs(a[i + x] - a[i + x - k]) > 1) return k - 1; 37 if (abs(a[x + k - 1] - a[y - k + 1]) <= 1) return k - 1; 38 } 39 return y - x + 1; 40 } 41 42 int main(){ 43 int i, j; 44 while (scanf("%d", &n) != EOF){ 45 for (i = 1; i <= n; ++i) 46 scanf("%d", a + i); 47 sort(a + 1, a + n + 1); 48 memset(f, 0, sizeof(f)); 49 for (i = 1; i <= n; ++i) 50 for (j = 0; j < i; ++j) 51 f[i] = max(f[i], f[j] + calc(j + 1, i)); 52 printf("%d ", f[n]); 53 } 54 return 0; 55 }