蛮妙的题 满满的TC味
考虑一种木偶与绳索配对的方法： AwD orz
木偶 1 与绳索k 1配对，木偶 2 与绳索k 2配对……木偶 n−k 与绳索 n 配对。 当木偶n−k 1无法与绳索 k 配对时，这样的配对方法能扔掉k个木偶。
然后就可以DP了
#include<cstdio> #include<cstdlib> #include<algorithm> #define read(x) (scanf("%d",&(x))) using namespace std; const int N=105; int n; int f[N],a[N]; int g[N][N]; int main(){ freopen("t.in","r",stdin); freopen("t.out","w",stdout); while (~read(n)){ for (int i=1;i<=n;i++) read(a[i]); sort(a+1,a+n+1); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++){ int flag=0; for (int k=1;k<=j-i+1;k++){ int t; for (t=0;i+k+t<=j;t++) if (a[i+k+t]-a[i+t]>1) flag=1; if (abs(a[i+t]-a[i+k-1])<=1) flag=1; if (flag) { g[i][j]=k-1; break; } } if (!flag) g[i][j]=j-i+1; } for (int i=0;i<=n;i++) f[i]=0; for (int i=1;i<=n;i++) for (int j=0;j<i;j++) f[i]=max(f[i],f[j]+g[j+1][i]); printf("%d\n",f[n]); } return 0; }