BZOJ2708: [Violet 1]木偶

Portal

Sample Input 1

2

1

54

2

8 9

3

1 2 3

2

56 60

3

59 59 57

3

51 55 59

5

1 2 3 2 4

4

87 70 81 34

4

50 55 58 59

6

1 2 3 4 5 6

6

1 2 3 3 4 5

8

1 2 3 3 4 2 5 4

9

22 23 52 61 39 38 1 40 17

Sample Output 0

0

0

1

0

0

0

1

0

0

2

2

2

1

先排序 假如将木偶和提线分别对应放为两列，配对的相连。那么最优的答案应该是形如： f[i] 表示前 i 对，最多能丢弃的个数。 f[i]=f[j] Cal(j 1,i) Cal过程枚举一条线跨越区间长度，然后检验。 过程看看代码意会一下。。

【代码】

#include <iostream> #include <cstdio> #include <algorithm> #define N 1000005 #define mod 1000000 #define INF 1e9 using namespace std; typedef long long ll; int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int n; int f[N],a[N]; int Cal(int x,int y) { for(int k=1;k<=y-x+1;k++) { if(abs(a[x+k-1]-a[y-k+1])<=1) return k-1; for(int i=k;i<=y-x;i++) if(abs(a[i+x]-a[i+x-k])>1) return k-1; } return y-x+1; } int main() { while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) a[i]=read(),f[i]=0; sort(a+1,a+1+n); 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\n",f[n]); } return 0; }