题意:链接
方法: DP
解析:
这题太神辣。
做梦都没想到DP啊，反正我不会。
先谈一个我有过的错的想法。
最小费用最大流？
能匹配的边连费用为1的，不能匹配的连费用为0的
跑最小费用最大流
然而这显然是错的。我还思考半天。
由于这道题强制假设还用费用为1的边。那必须先跑费用为1的边。
这样就不符合辣
至于自己改下这个写法？
尝试过- -。然而卡在哪里呢？
一堆费用为1的边你先跑那个呢？- -评估？评估函数怎么写啊，我不会啊。
所以这个写法显然弃疗。
然而我还曾有过一个想法。
贪心？
对于每个值pi来说。我们统计一下Num，然后呢
我们来考虑拿最大的Num。最大的Num怎么拿呢？
让他没有匹配的对象，或是尽可能的使他能匹配的对象都跟别人匹配。然后Num-他还能匹配的对象就是这一轮操作的答案。
每匹配一次更新一遍，直到Num都为0
只是这正确性有点可怜…
总感觉是错的。
好像上一个方法的错误部分就能卡住这个？
应该吧，反正我没实现。
但总感觉贪心有路子，可是我不会啊。
正解
正解好神并且好简洁啊。
排一下序
然后设f[i]为前i个最多扔多少个。
f[i]=max(f[j],cal(j+1,i))
这个cal是什么呢
我们枚举能扔多少个。
然后验证，
并且验证的时候是依照什么样子匹配呢？
有序之后就这么匹配即可辣
正确性？不会证明啊，应该看起来是对的
复杂度？n这么小谈什么复杂度。
15.10.27 Update：
对于例子 1 2 3 3 4 5的解释。
假设依照上述分段的思想。
可能会这样匹配
1 2 3 3 4 5
2 3 1 4 5 3
这种话。木偶会剩下 3 5。而提线剩下1 3。还能够继续匹配。
并不符合上述解法。
事实上仅仅在于一个点上-》就是不同的段上的匹配方式是互逆的。
1 2 3
2 3 1 依照这种方式。
3 4 5
5 3 4 仅仅要是上一段的逆序匹配即可，就不会出现矛盾的情况。
代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 55
using namespace std;
int f[N];
int a[N];
int n;
int cal(int x,int y)
{
for(int k=1;k<=y-x+1;k++)
{
for(int j=x;j<=y-k;j++)
if(abs(a[j]-a[j+k])>1)return k-1;
if(abs(a[x+k-1]-a[y-k+1])<=1)return k-1;
}
return y-x+1;
}
int main()
{
while(~scanf("%d",&n))
{
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
f[i]=max(f[i],f[j]+cal(j+1,i));
printf("%d
",f[n]);
}
}