题意：
有n张牌，每张牌上都有一个不超过n的正整数，你可以选择三张数字连续的牌作为一个顺子，也可以选择两张数字一样的牌作为一个对子，现要让对子和顺子的数量之和尽可能多，求最大数量
先排序
因为对子只消耗两张牌，所以尽可能组成对子
那么如果某个数字的牌超过两张，就将多余的全部组成对子直到剩下两张或一张
然后就可以dp了，dp[i]表示（剩下的）前i张牌组成对子+顺子数量和的最大值
有dp[i] = max(dp[i-1], dp[i-2]+1(a[i]==a[i-1]), dp[i-3]+1(a[i]==a[i-1]+1 && a[i-1]==a[i-2]+1))
#include<stdio.h> #include<algorithm> using namespace std; int a[1000005], dp[1000005]; int main(void) { int n, i, ans, cnt; while(scanf("%d", &n)!=EOF) { cnt = ans = 0; for(i=1;i<=n;i++) scanf("%d", &a[i]); sort(a+1, a+n+1); for(i=1;i<=n;i++) { if(cnt>=2 && a[i]==a[cnt] && a[cnt]==a[cnt-1]) { cnt--, ans++; continue; } a[++cnt] = a[i]; } for(i=2;i<=cnt;i++) { dp[i] = dp[i-1]; if(i>=2 && a[i]==a[i-1]) dp[i] = max(dp[i], dp[i-2]+1); if(i>=3 && a[i]==a[i-1]+1 && a[i-1]==a[i-2]+1) dp[i] = max(dp[i-3]+1, dp[i]); } printf("%d\n", ans+dp[cnt]); } return 0; }
