BZOJ 2708 木偶

mac2025-07-18  2

#include <bits/stdc++.h> using namespace std; const int N=55; int n; int a[N],f[N]; inline bool pd(int l,int r,int x) { if (l+x-1>=r-x+1 || abs(a[l+x-1]-a[r-x+1])<=1) return false; //如果,l+x-1>=r-x+1,那么,都已经重复了,不会舍弃那么多的 //如果a[l+x-1]和a[r-x+1]可以匹配成一个(紫色线条连起来的两个点),那么,肯定不能做到舍弃x个了 for (register int i=l; i<=r-x; ++i) if (a[i+x]-a[i]>1) return false; //当每一个a[i+x]和a[i]都可以恰好匹配的时候(红色线条连起来的那些点对),就说明方案可行了 return true; } inline int solve(int l,int r) { //枚举这段区间最多能舍弃几个 for (register int i=1; i<=r-l+1; ++i) if (!pd(l,r,i)) return i-1; } int main(){ while (~scanf("%d",&n)) { memset(f,0,sizeof(f)); for (register int i=1; i<=n; ++i) scanf("%d",&a[i]); sort(a+1,a+n+1); //f[i]表示:排完序后,前i个,最多能舍弃多少个 for (register int i=1; i<=n; ++i) for (register int j=0; j<i; ++j) f[i]=max(f[i],f[j]+solve(j+1,i)); printf("%d\n",f[n]); } return 0; }
最新回复(0)