题意：给你n个数，问你最多能组成多少顺子和对子
题解：和bzoj上的一道题类似，不过bzoj上对子是3张牌，所以无脑先选对子即可，然而这道题对子是
两张牌，因此之前的贪心还是有些问题的，比如： 1 2 3 3 4 5 ，答案应该是2,。
但是我们仍然可以考虑先选对子，然后让每种牌最多留下一个对子（可以自己证明，留的多了没用）
然后我们判断留下的对子能否组成两个顺子即可，当然遍历的过程中顺子也都找出来了。。
#include<set> #include<map> #include<stack> #include<queue> #include<vector> #include<string> #include<math.h> #include<stdio.h> #include<iostream> #include<string.h> #include<stdlib.h> #include<algorithm> #include<functional> using namespace std; typedef long long ll; #define inf 1000000000 #define mod 1000000007 #define maxn 2600005 #define PI acos(-1.0) #define lowbit(x) (x&-x) #define eps 1e-9 int a[maxn], b[maxn], dp[maxn]; int main(void) { int n, i, j, k, ans; while (scanf("%d", &n) != EOF) { ans = 0; memset(b, 0, sizeof(b)); memset(dp, 0, sizeof(dp)); for (i = 1;i <= n;i++) scanf("%d", &a[i]), b[a[i]]++; for (i = 1;i <= n;i++) { if (b[i] <= 2) continue; ans += b[i] / 2; if (b[i] % 2 == 0) ans--; b[i] = 2 - (b[i] % 2 == 1); } dp[1] = b[1] / 2; if (b[1] > 1) b[1] = 0; dp[2] = dp[1] + b[2] / 2; if (b[2] > 1) b[2] = 0; for (i = 3;i <= n;i++) { dp[i] = dp[i - 1]; if (b[i] == 0) continue; if (b[i] > 1) dp[i] = dp[i - 1] + 1; if (b[i - 1] && b[i - 2] && dp[i] <= dp[i - 2] + 1) dp[i] = dp[i - 2] + 1, b[i]--, b[i - 1]--, b[i - 2]--; else if (b[i - 1] && b[i - 2] && dp[i] > dp[i - 2] + 1 || b[i - 1] == 0 || b[i - 2] == 0) { if (b[i] > 1) b[i] = 0; } //printf("%d %d\n", dp[i], i); } printf("%d\n", ans + dp[n]); } return -1; } /* 10 1 1 1 2 3 4 5 6 7 8 9 1 2 3 6 7 8 8 9 10 */
