题面
这好像就是道**暴搜题, 由于可以回溯, 所以顺序其实没有多大的关系, 见代码吧...
具体代码
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int T, n, cnt[20], ans;
inline int read()
{
int x = 0, w = 1;
char c = getchar();
while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
return x * w;
}
void dfs(int);
void SHUN(int x, int y, int step)
{
int k = 0;
for(int i = 1; i <= 12; i++)
{
if(cnt[i] < x) k = 0;//如果中间断开了就需要重新计算了, 难道你打顺子还打一个3,4,5,7,8,9,10吗??? 你会被和你一起打牌的人群殴一顿了...
else
{
k++;
if(k >= y)
{
for(int j = i; j >= i - k + 1; j--) cnt[j] -= x;
dfs(step + 1);
for(int j = i; j >= i - k + 1; j--) cnt[j] += x;
}
}
}
}
void DAI3(int x, int y, int step, int num)
{
for(int j = 1; j <= y; j++)
{
if(cnt[j] < x || j == num) continue;
cnt[j] -= x;
dfs(step + 1);
cnt[j] += x;
}//搜索和回溯, 不会的话去请你的教练给你复习一下吧
}
void DAI4(int x, int y, int step, int num)
{
for(int i = 1; i <= y; i++)//范围
{
if(cnt[i] < x || i == num) continue;
cnt[i] -= x;
for(int j = 1; j <= y; j++)
{
if(cnt[j] < x) continue;
//两张单牌应该可以打一样的吧...
cnt[j] -= x;
dfs(step + 1);
cnt[j] += x;
}
cnt[i] += x;
}//还是搜索与回溯
}
void dfs(int step)
{
if(step >= ans) return;
SHUN(3, 2, step); SHUN(2, 3, step); SHUN(1, 5, step);
//顺子SHUN(x,y,step)x的意思是顺子是几顺子, 也就是每张牌有多少张, y的意思是最少要几个连着的牌, 例如说单顺子就是五张起打嘛, step就是当前已经打了几次牌了...
for(int i = 1; i <= 13; i++)
{
if(cnt[i] <= 3)//带牌, 三带一之类的, DAI3(x,y,step,i)意思是带x张牌, 牌的范围是y, 我也不知道三带一为什么可以带个鬼, step同上, i是不能被重复用的牌, 你不可能把自己给带上吧...
{
if(cnt[i] <= 2) continue;
cnt[i] -= 3;
DAI3(1, 14, step, i); DAI3(2, 13, step, i);
cnt[i] += 3;
}
else
{
cnt[i] -= 4; //如果有四张牌的话可以打四张
DAI4(1, 14, step, i); DAI4(2, 13, step, i);//意思与上面DAI3差不多,就是x的意思有点不一样, 1是带两种单牌, 2是带两对对子...
cnt[i] += 1;//有四张牌的话当然可以打三张了啦
DAI3(1, 14, step, i); DAI3(2, 13, step, i);//同上DAI3解释
cnt[i] += 3;
}
}
for(int i = 1; i <= 14; i++) if(cnt[i]) step++; //带的, 顺子都打完了之后就只有单牌,对子,三张牌,炸弹和王炸了, 每个打出去就行了, 不管他是一张两张或者三张四张, 都可以一次性打完, 哦也
ans = min(ans, step); //更新答案数组
}
int main()
{
T = read(); n = read();
while(T--)
{
memset(cnt, 0, sizeof(cnt));
for(int i = 1; i <= n; i++)
{
int x = read(), y = read();
if(x == 0) x = 14;//x是大小鬼, 放在最大的十四的位置
else if(x == 1 || x == 2) x += 11;//x是A或者2, 放在12和13的位置
else if(x >= 3 && x <= 13) x -= 2;//其他的-=2
cnt[x]++;
//有没有发现, 其实是按牌的大小从小到大排列的, 毕竟扑克中是3,4,5,6,7,8,9,10,J,Q,K,A,2,鬼,
//其实是这样子好找顺子...
}
ans = n; dfs(0);
printf("%d
", ans);
}
//这道题其实就是考的细心, 好好写一下就好了...
return 0;
}
但是似乎过不了数据加强版, 吸氧也过不了, 自己再去剪点枝吧...