好，终于搞完了这一道毒瘤题......
先想到搜索，然后想到状压，发现数据组数很多，又是随机，还是决定用搜索。
先搜出的多的，于是顺序是三个顺子，然后按照多到少搜带牌，最后是不带牌。
大体思路很简单，写起来很毒瘤...
注意很多细节...我就是一个地方没写上界导致数组越界了。
三带一别带自己，因为可以算在4不带里。
王可以当对子出，当单牌带，但是不能当对牌带。
4带2对是存在的。
王的读入是0 1和0 2，中间有空格...
函数调用我写的很多，复制粘贴时别写混了。
变量++找牌的时候，要规定上界。
大概就是这些了。
代码6K...
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = ; int n, ans;
int bin[]; inline void out() {
for(int i = ; i <= ; i++) {
printf("%3d", bin[i]);
}
printf("%3d\n", bin[]);
return;
} inline void read() {
int x;
scanf("%d", &x);
if(x) {
if(x < ) {
x += ;
}
bin[x]++;
}
else {
bin[]++;
}
scanf("%d", &x);
return;
}
void DFS(int, int, int); void one_link(int rest, int time, int t, int pos) {
int l = std::max(pos, );
while(!bin[l] && l <= ) {
l++;
}
if(l >= ) {
DFS(rest, time, t + );
return;
}
int r = l + ;
while(r < && bin[r]) {
r++;
} if(r - l >= ) {
for(int j = l + ; j <= r; j++) {
for(int i = l; i < j; i++) {
bin[i]--;
}
one_link(rest - (j - l), time + , t, l);
for(int i = l; i < j; i++) {
bin[i]++;
}
}
}
one_link(rest, time, t, l + );
return;
} void two_link(int rest, int time, int t, int pos) {
int l = std::max(pos, );
while(bin[l] < && l <= ) {
l++;
}
if(l >= ) {
DFS(rest, time, t + );
return;
}
int r = l + ;
while(r < && bin[r] > ) {
r++;
} if(r - l >= ) {
for(int j = l + ; j <= r; j++) {
/// [l, j)
for(int i = l; i < j; i++) {
bin[i] -= ;
}
two_link(rest - * (j - l), time + , t, l);
for(int i = l; i < j; i++) {
bin[i] += ;
}
}
}
two_link(rest, time, t, l + );
return;
} void three_link(int rest, int time, int t, int pos) {
int l = std::max(pos, );;
while(bin[l] < && l <= ) {
l++;
}
if(l >= ) {
DFS(rest, time, t + );
return;
}
int r = l + ;
while(r < && bin[r] > ) {
r++;
} if(r - l >= ) {
for(int j = l + ; j <= r; j++) {
/// [l, j)
for(int i = l; i < j; i++) {
bin[i] -= ;
}
three_link(rest - * (j - l), time + , t, l);
for(int i = l; i < j; i++) {
bin[i] += ;
}
}
if(r - l > ) {
three_link(rest, time, t, l + );
}
else {
three_link(rest, time, t, r + );
}
}
else {
three_link(rest, time, t, r + );
}
return;
} void four_four(int rest, int time, int t, int pos) {
int p = std::max(pos, );
while(bin[p] < && p <= ) {
p++;
}
if(p == ) {
DFS(rest, time, t + );
return;
}
bin[p] -= ;
for(int i = ; i <= ; i++) {
if(bin[i] > ) {
bin[i] -= ;
for(int j = i; j <= ; j++) {
if(bin[j] > ) {
bin[j] -= ;
four_four(rest - , time + , t, p);
bin[j] += ;
}
}
bin[i] += ;
}
}
bin[p] += ;
four_four(rest, time, t, p + );
return;
} void four_two(int rest, int time, int t, int pos) {
int p = std::max(pos, );
while(bin[p] < && p <= ) {
p++;
}
if(p == ) {
DFS(rest, time, t + );
return;
}
bin[p] -= ;
for(int i = ; i <= ; i++) {
if(bin[i]) {
bin[i]--;
for(int j = i; j <= ; j++) {
if(bin[j]) {
bin[j]--;
four_two(rest - , time + , t, p);
bin[j]++;
}
}
bin[i]++;
}
}
bin[p] += ;
four_two(rest, time, t, p + );
return;
} void three_two(int rest, int time, int t, int pos) {
int p = std::max(, pos);
while(bin[p] < && p <= ) {
p++;
}
if(p == ) {
DFS(rest, time, t + );
return;
}
bin[p] -= ;
for(int i = ; i <= ; i++) {
if(bin[i] > ) {
bin[i] -= ;
three_two(rest - , time + , t, p);
bin[i] += ;
}
}
bin[p] += ;
three_two(rest, time, t, p + );
return;
} void three_one(int rest, int time, int t, int pos) {
int p = std::max(pos, );
while(bin[p] < && p <= ) {
p++;
}
if(p == ) {
DFS(rest, time, t + );
return;
}
bin[p] -= ;
for(int i = ; i <= ; i++) {
if(bin[i] && i != p) {
bin[i]--;
three_one(rest - , time + , t, p);
bin[i]++;
}
}
bin[p] += ;
three_one(rest, time, t, p + );
return;
} void DFS(int rest, int time, int t) {
if(!rest) {
ans = std::min(ans, time);
return;
}
if(time >= ans - ) {
return;
}
if(!t) {
one_link(rest, time, t, );
}
else if(t == ) {
two_link(rest, time, t, );
}
else if(t == ) {
three_link(rest, time, t, );
}
else if(t == ) {
four_four(rest, time, t, );
}
else if(t == ) {
four_two(rest, time, t, );
}
else if(t == ) {
three_two(rest, time, t, );
}
else if(t == ) {
three_one(rest, time, t, );
}
else {
int a = ;
for(int i = ; i <= ; i++) {
a += (bin[i] > );
}
ans = std::min(ans, time + a);
}
return;
} inline void solve() {
ans = ;
for(int i = ; i <= ; i++) {
ans += (bin[i] > );
}
DFS(n, , );
printf("%d\n", ans);
return;
} int main() {
int T;
scanf("%d%d", &T, &n);
while(T--) {
for(int i = ; i <= n; i++) {
read();
}
solve();
if(T) {
memset(bin, , sizeof(bin));
}
} return ;
}
AC代码
顺手把增强版也A了，跑的贼快。
数组300000是之前调的，忘了改回来。