题解 - Vijos

2

call_me_std LV 8 @ 2017-10-25 21:57:32

有点坑，看起来很吓人，写起来还是比较好写的吧。
注意三带一和四带二都可以带王

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int T,n;
int cnt[17],ans=99;
const int size[4]={0,5,3,2};
void dfs(int x)
{
    if(x>ans) return;
    for(int i=3;i;i--)//处理顺子,i是顺子中相同牌的个数
    {
        int l=0;
        for(int j=3;j<=14;j++)
        {
            if(cnt[j]>=i) l++;else l=0;
            if(l>=size[i])
            {
                for(int k=j-l+1;k<=j;k++) cnt[k]-=i;
                dfs(x+1);
                for(int k=j-l+1;k<=j;k++) cnt[k]+=i;
            }
        }
    }
    for(int i=2;i<=14;i++)//处理4带2,注意处理4带两对
    {
        if(cnt[i]>=4)
        {
            cnt[i]-=4;
            for(int j=2;j<=14;j++)
            {
                if(i==j||cnt[j]<2) continue;
                cnt[j]-=2;
                for(int k=2;k<=14;k++) 
                {
                    if(cnt[k]<2||k==j) continue;
                    cnt[k]-=2;dfs(x+1);cnt[k]+=2; 
                }
                cnt[j]+=2;
            }
            for(int j=2;j<=15;j++)
            {
                if(i==j||cnt[j]<1) continue;
                --cnt[j];
                for(int k=2;k<=15;k++)
                {
                    if(cnt[k]<1||k==j) continue;
                    --cnt[k];dfs(x+1);++cnt[k];
                }
                ++cnt[j];
            }
            cnt[i]+=4;
        }
    }
    for(int i=2;i<=14;i++)//处理3带(1\2)
    {
        if(cnt[i]>=3)//3带2
        {
            cnt[i]-=3;
            for(int j=2;j<=14;j++)
            {
                if(cnt[j]<2||i==j) continue;
                cnt[j]-=2;
                dfs(x+1);
                cnt[j]+=2;
            }
            for(int j=2;j<=15;j++)//3带1
            {
                if(cnt[j]<1||i==j) continue;
                --cnt[j];dfs(x+1);++cnt[j];
            }
            cnt[i]+=3;
        }
    }
    for(int i=2;i<=15;i++) if(cnt[i]>0) ++x;//剩下的牌只能每种相同的牌单独出，每种牌只用出一次
    ans=min(ans,x);
}
int main()
{
    T=read(),n=read();
    while(T--)
    {
        memset(cnt,0,sizeof(cnt));
        ans=99;
        for(int i=1;i<=n;i++){int x=read();if(x!=0)cnt[x]++;else cnt[15]++;x=read();}
        cnt[14]=cnt[1];dfs(0);printf("%d\n",ans);   
    }
    return 0;
}

1

linhui' LV 5 @ 2016-11-18 08:07:07

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int hand[5], ans;

struct Card{
int c[15], tep;
void clear(){
memset(c, 0, sizeof(c));
tep = 0;
}
void print(){
for(int i = 1; i <= 14; i++)
cout<<c[i]<<" ";
cout<<endl;
}
}start;

int clac(Card now){
int res = 0;
memset(hand, 0, sizeof(hand));
for(int i = 1; i <= 14; i++)
hand[now.c[i]]++;
if(now.c[14] == 2){
if(hand[4] && hand[2] >= 2) hand[4]--, hand[2]-=2, res++;
else if(hand[4] && hand[2]) hand[4]--, hand[2]--, res++;
else hand[2]--, res++;
}
while(hand[4] && hand[1] >= 2) hand[4]--, hand[1]-=2, res++;
while(hand[4] && hand[2] >= 2) hand[4]--, hand[2]-=2, res++;
while(hand[4] && hand[2]) hand[4]--, hand[2]--, res++;
while(hand[3] && hand[2]) hand[3]--, hand[2]--, res++;
while(hand[3] && hand[1]) hand[3]--, hand[1]--, res++;
res += hand[4] + hand[3] + hand[2] + hand[1];
return res;
}

void dfs(Card now){
int bri = now.tep + clac(now);
ans = min(ans, bri);

//单顺
for(int i = 1; i <= 8; i++){
int flag = 0;
for(int j = i; j <= i+4; j++)
if(!now.c[j]){
flag = 1;
break;
}
if(flag) continue;
Card ne = now;
ne.tep++;
for(int j = i; j <= i+4; j++) ne.c[j]--; //5张
dfs(ne);
for(int j = i+5; j <= 12; j++){ //5+张
if(ne.c[j]){
ne.c[j]--;
dfs(ne);
}
else
break;
}
}

//双顺
for(int i = 1; i <= 10; i++){
int flag = 0;
for(int j = i; j <= i+2; j++)
if(now.c[j] < 2){
flag = 1;
break;
}
if(flag) continue;
Card ne = now;
ne.tep++;
for(int j = i; j <= i+2; j++)
ne.c[j] -= 2;
dfs(ne);
for(int j = i+3; j <= 12; j++){
if(ne.c[j] >= 2){
ne.c[j] -= 2;
dfs(ne);
}
else
break;
}
}

//三顺
for(int i = 1; i <= 11; i++){
int flag = 0;
for(int j = i; j <= i+1; j++)
if(now.c[j] < 3){
flag = 1;
break;
}
if(flag) continue;
Card ne = now;
ne.tep++;
for(int j = i; j <= i+1; j++) ne.c[j] -= 3;
dfs(ne);
for(int j = i+2; j <= 12; j++){
if(ne.c[j] >= 3){
ne.c[j] -= 3;
dfs(ne);
}
else
break;
}
}
}

int main()
{
int T, n;
scanf("%d%d", &T, &n);
while(T--){
start.clear();
ans = n;
for(int i = 1; i <= n; i++){
int a, b;
scanf("%d%d", &a, &b);
if(a == 0) start.c[14]++;
else if(a == 1) start.c[12]++;
else if(a == 2) start.c[13]++;
else start.c[a-2]++;
}
start.tep = 0;
dfs(start);
printf("%d\n", ans);
}
return 0;
}
搜索

0

董鑫123 LV 4 @ 2021-02-02 23:10:52

//hbw2018
/*
斗地主
*/
#include<bits/stdc++.h>
#define PLAYERCOUNT 3
#define CARDSCOUNT 54
#define CURRENTPLAYER 0
#define VALUECOUNT 17
#define ERROR -1

using namespace std;
const char toFigure[]="34567890JQKA 2YZ";
enum COLOR{ //花色显示ASCII: 3~6
eHEART=3,//红桃
eDIAMOND,//方片
eCLUB, //草花
eSPADE //黑桃
};

class Card;
class CardsType;
class CardGroup;
class Player;
class Landlords;
class LastCards;
bool makeChoice(string tip);
bool cmp(Card* a,Card* b);

class Card{
public:
char figure;
COLOR color;
int value;
Card(char _figure,COLOR _color){
figure=_figure;
color=_color;
value=calValue();
}
int calValue(){
for(int i=0;toFigure[i];i++){
if(toFigure[i]==figure){
return i;
}
}
return ERROR;
}
void print(){
assert(value!=ERROR);
if(figure=='Z'){
cout<<"ZZ";
}else if(figure=='Y'){
cout<<"YY";
}else{
cout<<figure<<(char)color;
}
cout<<' ';
}
};

class CardsType{
public:
//为了规范查找对应牌的方法
//统一为3个参数cnt1、isContinuous、cnt2
int typeId;
string typeStr;
int cnt1,cnt2;
bool isContinuous;
CardsType(){
typeId=ERROR;
}
bool operator ==(const CardsType& other)const{
return this->typeId==other.typeId;
}
void init(char* _typeStr,int _typeId,int _cnt1,bool _isContinuous,int _cnt2){
cnt1=_cnt1;
isContinuous=_isContinuous;
cnt2=_cnt2;
typeStr=_typeStr;
typeId=_typeId;
}
};

class CardGroup{
public:
vector<Card*> cards;
CardsType type;
void calType(){
int i,n=cards.size();
//init(typeStr,typeId,cnt1,isContinuous,cnt2)
if(n==0){
type.init("不出",14,0,0,0);
return;
}
if(n==2&&cards[0]->value==15&&cards[1]->value==14){
type.init("王炸",0,0,0,0);
return;
}
//统计同点数牌有多少张
int cntFlag[VALUECOUNT]={0};
for(i=0;i<n;i++){
cntFlag[cards[i]->value]++;
}
//统计点数最多和最少的牌
int maxCnt=0,minCnt=4;
for(i=0;i<VALUECOUNT;i++){
if(maxCnt<cntFlag[i]){
maxCnt=cntFlag[i];
}
if(cntFlag[i]&&minCnt>cntFlag[i]){
minCnt=cntFlag[i];
}
}
if(n==4&&maxCnt==4){
type.init("炸dan",1,4,0,0);
return;
}
if(n==1){
type.init("单牌",2,1,0,0);
return;
}
if(n==2&&maxCnt==2){
type.init("对子",3,2,0,0);
return;
}
if(n==3&&maxCnt==3){
type.init("三张 ",4,3,0,0);
return;
}
if(n==4&&maxCnt==3){
type.init("三带一",5,3,0,1);
return;
}
if(n==5&&maxCnt==3&&minCnt==2){
type.init("三带一对",6,3,0,2);
return;
}
if(n==6&&maxCnt==4){
type.init("四带二",7,4,0,1);
return;
}
if(n==8&&maxCnt==4&&minCnt==2){
type.init("四带二",8,4,0,2);
return;
}
if(n>=5&&maxCnt==1&&cards[0]->value==cards[n-1]->value+n-1){
type.init("顺子",9,1,1,0);
return;
}
if(n>=6&&maxCnt==2&&minCnt==2&&cards[0]->value==cards[n-1]->value+n/2-1){
type.init("连对",10,2,1,0);
return;
}
int fjCnt;//统计连续且大于3三张的牌
for(i=0;i<VALUECOUNT &&cntFlag[i]<3;i++);
for(fjCnt=0;i<VALUECOUNT &&cntFlag[i]>=3;i++,fjCnt++);
if(fjCnt>1){
if(n==fjCnt*3)
type.init("飞机",11,3,1,0);
else if(n==fjCnt*4)
type.init("飞机",12,3,1,1);
else if(n==fjCnt*5&&minCnt==2)
type.init("飞机",13,3,1,2);
}
}
void init(string inputStr, vector<Card*> &cardsHolded){
this->cards.clear();
//不出
if(inputStr=="N"){
this->calType();
return;
}
int i,j;
//输入合法性判断
for(i=0;i<inputStr.size();i++){
bool find=false;
for(j=0;toFigure[j];j++){
if(inputStr[i]==toFigure[j]){
find=true;
break;
}
}
if(find==false){
//输入字符不在toFigure中
return;
}
}
//查找手中有没有这些牌
int visitFlag[20]={0};
for(i=0;i<inputStr.size();i++){
Card *find=NULL;
for(j=0;j<cardsHolded.size();j++){
if(!visitFlag[j]&&cardsHolded[j]->figure==inputStr[i]){
visitFlag[j]=1;
find=cardsHolded[j];
break;
}
}
if(find){
this->cards.push_back(find);
}else{
cout<<inputStr[i];
cout<<"没有找到\t";
this->cards.clear();
return;
}
}//end for(i=0;i<inputStr.size();i++)
this->arrange();
}
void init(vector<Card*> newCards){
this->cards=newCards;
this->arrange();
}
bool isCanBeat(CardGroup &cardGroup){
if(cardGroup.type.typeStr=="王炸"){
return false;
}else if(this->type.typeStr=="王炸"){
return true;
}else if(cardGroup.type==this->type &&this->type.typeStr=="炸dan"){
return value()>cardGroup.value();
}else if(cardGroup.type.typeStr=="炸dan"){
return false;
}else if(this->type.typeStr=="炸dan"){
return true;
}else if(cardGroup.type==this->type &&this->cards.size()==cardGroup.cards.size()){
return this->value()>cardGroup.value();
}else{
return false;
}
}
int value(){
//计算牌组权值
int i;
if(type.typeStr=="三带一"||type.typeStr=="三带一对"||type.typeStr=="飞机"){
for(i=2;i<cards.size();i++){
if(cards[i]->value==cards[i-2]->value){
return cards[i]->value;
}
}
}
if(type.typeStr=="四带二"){
for(i=3;i<cards.size();i++){
if(cards[i]->value==cards[i-3]->value){
return cards[i]->value;
}
}
}
return cards[0]->value;
}
void arrange(){
//整理：排序、计算类型
sort(this->cards.begin(),this->cards.end(),cmp);
this->calType();
}
};
class LastCards{
static LastCards *lastCards;
public:
Player player;
CardGroup cardGroup;
static LastCards inst(){//单例模式
if(lastCards==NULL){
lastCards=new LastCards();
}
return lastCards;
}
vector<Card*> findCanBeatFrom(vector<Card*> &cardsHolded){
//查找能打得过的牌
int i,j,k,n=cardsHolded.size(),m=cardGroup.cards.size();
string typeStr=cardGroup.type.typeStr;
vector<Card*> ret;
if(typeStr=="王炸"||n<m){
//打不过，返回空数组
return ret;
}
int value=cardGroup.value();
//统计各点牌出现的次数
int cntFlag[VALUECOUNT]={0};
for(i=0;i<n;i++){
cntFlag[cardsHolded[i]->value]++;
}
int continuousCount=1;
if(cardGroup.type.isContinuous){
continuousCount=m/(cardGroup.type.cnt1+cardGroup.type.cnt2);
}
bool findFirstFigure;
//cout<<"continuousCount="<<continuousCount<<endl;
for(i=value+1;i<VALUECOUNT;i++){
findFirstFigure=true;
for(j=0;j<continuousCount;j++){
if(cntFlag[i-j]<cardGroup.type.cnt1){
findFirstFigure=false;
break;
}
}
if(findFirstFigure){
ret.clear();
int firstFigure=i;
//cout<<"查找"<<cardGroup.type.cnt1<<"个"<<firstFigure+3<<endl;
for(k=0,j=0;k<cardsHolded.size() &&j<continuousCount;k++){
if(cardsHolded[k]->value==firstFigure-j){
for(int kk=0;j>=0&&kk<cardGroup.type.cnt1;kk++){
ret.push_back(cardsHolded[k+kk]);
}
j++;
}
}
if(cardGroup.type.cnt2>0){
int SecondFigures[5];
int SecondCount=continuousCount;
if(cardGroup.type.typeStr=="四带二")
SecondCount=2;
bool findSecondFigure=true;
for(j=0,k=-1;j<SecondCount &&findSecondFigure;j++){
findSecondFigure=false;
for(k++;k<VALUECOUNT;k++){
SecondFigures[j]=k;
if(cntFlag[k]>=cardGroup.type.cnt2 &&cntFlag[k]<cardGroup.type.cnt1){
findSecondFigure=true;
break;
}
}
}
if(findSecondFigure){
//cout<<"查找SecondFigure "<<cardGroup.type.cnt2<<"个"<<SecondFigures[0]+3<<endl;
//cout<<"SecondCount= "<<SecondCount<<endl;
//for(i=0;i<SecondCount;i++)cout<<"SecondFigures["<<i<<"]="<<SecondFigures[i]<<endl;
for(i=0;i<SecondCount;i++){
for(j=0;j<cardsHolded.size();){
if(cardsHolded[j]->value==SecondFigures[i]){
for(k=0;k<cardGroup.type.cnt2;k++){
//cout<<"添加"<<cardsHolded[j]->value+3<<endl;
ret.push_back(cardsHolded[j+k]);
}
do{
j++;
}while(j<cardsHolded.size()&&cardsHolded[j]->value==SecondFigures[i]);
}else{
j++;
}
}
}
return ret;
}//if(findSecondFigure)
}//end if(cardGroup.type.cnt2>0)
else{
return ret;
}
}//end if(findFirstFigure)
}//end for(i=value+1;i<VALUECOUNT;i++)
ret.clear();
//没牌打得过时查找有没有炸dan
if(typeStr!="炸dan"){
for(i=cardsHolded.size()-1;i>=3;i--){
if(cardsHolded[i]->value==cardsHolded[i-3]->value){
for(j=0;j<4;j++){
ret.push_back(cardsHolded[i-j]);
}
break;
}
}
}
return ret;
}//end vector<Card*> findCanBeatFrom()
};
LastCards* LastCards::lastCards = NULL;

class Player{
public:
string name;
vector<Card*> cards;
void arrange(){
sort(cards.begin(),cards.end(),cmp);
}
void print(){
cout<<this->name<<":\t";
for(int i=0;i<cards.size();i++){
cards[i]->print();
}
cout<<"["<<cards.size()<<"]\n";
}
vector<Card*> tip(){
//提示功能,使自己最小一张连最长
CardGroup ret;
string temp;
int j,k,m=cards.size();
for(j=0;j<m;j++){
temp="";
for(k=j;k<m;k++){
temp+=cards[k]->figure;
}
ret.init(temp,cards);
if(ret.type.typeId!=ERROR){
return ret.cards;
}
}
ret.cards.clear();
return ret.cards;
}
void chupai(CardGroup &cardGroup){
//出牌
cout<<this->name<<":\t";
cout<<cardGroup.type.typeStr<<' ';
for(int i=0;i<cardGroup.cards.size();i++){
cardGroup.cards[i]->print();
this->cards.erase(find(this->cards.begin(),this->cards.end(),cardGroup.cards[i]));
}
cout<<"\t["<<this->cards.size()<<"]\n";
if(cardGroup.type.typeStr!="不出"){
//记录到 LastCards 中
LastCards::inst()->player=this;
LastCards::inst()->cardGroup.init(cardGroup.cards);
}
}
};

class Landlords{
Player *player[PLAYERCOUNT];
bool finished,youWin,landlordWin;
int landlordIndex;
Card *cards[CARDSCOUNT];
public:
Landlords(){
int i,j,k;
for(i=0;i<PLAYERCOUNT;i++){
this->player[i]=new Player();
}
//54张牌初始化
for(k=i=0;i<14;i++){
if(toFigure[i]==' '){
continue;
}
for(COLOR color=eHEART;color<=eSPADE;color=(COLOR)(color+1)){
this->cards[k++]=new Card(toFigure[i],color);
}
}
this->cards[k++]=new Card('Y',eSPADE);
this->cards[k]=new Card('Z',eHEART);
}
~Landlords(){
for(int i=0;i<PLAYERCOUNT;i++){
delete this->player[i];
}
for(int i=0;i<CARDSCOUNT;i++){
delete this->cards[i];
}
}
void init(){
player[CURRENTPLAYER]->name="Bice";
player[1]->name="玩家2";
player[2]->name="玩家3";
finished=false;
youWin=false;
landlordWin=false;
//抢地主
landlordIndex=ERROR;
while(landlordIndex==ERROR){
srand((int)time(0));
shuffle();
landlordIndex=chooseLandlord();
}
cout<<player[landlordIndex]->name<<"\t成为地主\n\n";
this->add3Cards();
LastCards::inst()->player=player[landlordIndex];
}
void startGame(){
string inputSrt;
CardGroup inputCards;
for(int iTurns=landlordIndex;!finished;iTurns++){
if(iTurns>=PLAYERCOUNT){
iTurns=0;
}
if(iTurns==CURRENTPLAYER){
cout<<endl;
player[iTurns]->print();
cout<<"输入提示：Z=大王 Y=小王 0=10 输入可无序例如:JKQ0A9\n请出牌：\t";
do{
cin>>inputSrt;
inputCards.init(inputSrt,player[iTurns]->cards);
}while(check(&inputCards)==false);
}else{
if(player[iTurns]==LastCards::inst()->player){
//若是上次出牌的是自己，启用提示功能
inputCards.init(player[iTurns]->tip());
}else{
//查找能打得过上家的牌
inputCards.init(LastCards::inst()->findCanBeatFrom(player[iTurns]->cards));
}
}
player[iTurns]->chupai(inputCards);//出牌

if(player[iTurns]->cards.size()==0){
//玩家手中没牌了，游戏结束
finished=true;
landlordWin=iTurns==landlordIndex;
if(landlordWin){
youWin=landlordIndex==CURRENTPLAYER;
}else{
youWin=landlordIndex!=CURRENTPLAYER;
}
}
}
cout<<"\n_________________________ "<<(youWin?"You Win!":"You Lose!")<<" _________________________\n\n";
}
void add3Cards(){
cout<<"地主3张牌:\t";
for(int i=PLAYERCOUNT*17;i<CARDSCOUNT;i++){
this->cards[i]->print();
player[landlordIndex]->cards.push_back(cards[i]);
}
cout<<endl;
player[landlordIndex]->arrange();
}
int chooseLandlord(){
cout<<"\n_________________________ 抢地主 _________________________\n\n";
int first=-1,last,cnt=0,i,j=rand()%PLAYERCOUNT;
bool decision;
for(i=0;i<PLAYERCOUNT;i++,j==2?j=0:j++){
if(j==CURRENTPLAYER){
decision=makeChoice("是否抢地主？(Y=抢/N=不抢):");
}else{
decision=rand()%2;
}
if(decision){
cnt++;
last=j;
if(first==-1){
first=j;
}
cout<<this->player[j]->name<<"\t抢地主\n";
}else{
cout<<this->player[j]->name<<"\t没有抢\n";
}
}
if(cnt==0){
cout<<"没人抢，重新发牌\n";
return ERROR;
}
if(cnt==1){
//第一轮只有一人抢地主
return first;
}
else{
//最后一次争抢
if(first==CURRENTPLAYER){
decision=makeChoice("是否抢地主？(Y=抢/N=不抢):");
}else{
decision=rand()%2;
}
if(decision){
cout<<this->player[first]->name<<"\t抢地主\n";
return first;
}else{
cout<<this->player[first]->name<<"\t没有抢\n";
return last;
}
}
}
void shuffle(){
int i,j,k;

//洗牌
for(i=0;i<CARDSCOUNT;i++){
swap(this->cards[i],this->cards[rand()%CARDSCOUNT]);
}

//分牌
for(k=i=0;i<PLAYERCOUNT;i++){
this->player[i]->cards.clear();
for(j=0;j<17;j++){
this->player[i]->cards.push_back(this->cards[k++]);
}
this->player[i]->arrange();//整理
this->player[i]->print();
}
}
bool check(CardGroup *cardGroup){
if(cardGroup->type.typeId==ERROR){
cout<<"出牌错误，重新输入\n";
return false;
}else if(cardGroup->type.typeStr=="不出"){
return true;
}else if(LastCards::inst()->player!=player[CURRENTPLAYER]&&!cardGroup->isCanBeat(LastCards::inst()->cardGroup)){
cout<<"打不过，重新输入\n";
return false;
}else{
return true;
}
}
};

int main(){
Landlords *landlords=new Landlords();
do{
landlords->init();//发牌、抢地主
landlords->startGame();//游戏开始
}while(makeChoice("\n是否继续游戏？（Y=继续/N=结束）: "));
delete landlords;
return 0;
}

bool makeChoice(string tip){
cout<<tip;
string input;
cin>>input;
return input=="Y"||input=="y";
}

bool cmp(Card* a,Card* b){
//比较两张牌大小
if(a->value==b->value){
return a->color>b->color;
}else{
return a->value>b->value;
}
}

董鑫123 @ 2021-02-02 23:14:03

好像还有点问题

0

不知云 LV 8 @ 2017-11-06 20:15:39

dp[i][j][k][l][m]表示不考虑顺子的情况下，（数码相同的牌有四张的有i种【emmm也就是不算王炸的纯炸弹有x个】，以此类推，有三张的有j种，两张的有k种，一张的有l种，特别的，王的数量为m个）的情况，最少能够出完牌的次数。
王之所以分开考虑是因为王炸不能算对子，四带两对和三带一对的情况对于王炸要分开考虑，与其特判不如直接新开一维记录
先预处理出能够用得到的dp数组的值，然后dfs枚举顺子
本来dp数组中没有考虑拆牌的情况，只有十多行的状态转移，洛谷上面的原版斗地主能够a掉，但是洛谷的斗地主加强版和vijos的斗地主都不行
于是狠心把所有能够考虑到的拆牌的情况都写了进去，令人窒息的五十行if......
其实有的拆牌情况可以不用考虑的，只是我当时实在是不想思考了......
幸好一遍过，没有怎么调试，否则我会疯的......

 #include <stdio.h>
#include <algorithm>
#include <string.h>
#define MAX4 7
#define MAX3 9
#define MAX2 14
#define MAX1 25
#define MAX0 2
using namespace std;
int T,n;
int card[30];
int dp[8][10][15][26][3];
int finalans;
inline int read()
{
    int k=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){k=k*10+c-'0';c=getchar();}
    return k*f;
}
inline void DpBuild()
{
    for(int i=0;i<=MAX4;i++)
    {
        for(int j=0;j<=MAX3;j++)
        {
            for(int k=0;k<=MAX2;k++)
            {
                for(int l=0;l<=MAX1;l++)
                {
                    for(int m=0;m<=MAX0;m++)
                    {
                        dp[i][j][k][l][m]=i+j+k+l+(m==0?0:1);
                    }
                }
            }
        }
    }
    for(int i=0;i<=MAX4;i++)
    {
        int usingj=(MAX1-4*i)/3+1;
        for(int j=0;j<=usingj;j++)
        {
            int usingk=(MAX1-4*i-3*j)/2+1;
            for(int k=0;k<=usingk;k++)
            {
                int usingl=(MAX1-4*i-3*j-2*k)+1;
                for(int l=0;l<=usingl;l++)
                {
                    for(int m=0;m<=MAX0;m++)
                    {
                        if(m>1) dp[i][j][k][l][m]=min(dp[i][j][k][l][m-2]+1,dp[i][j][k][l][m]);
                        if(m>0) dp[i][j][k][l][m]=min(dp[i][j][k][l][m-1]+1,dp[i][j][k][l][m]);
                        if(i>0) dp[i][j][k][l][m]=min(dp[i-1][j][k][l][m]+1,dp[i][j][k][l][m]);
                        if(l>0) dp[i][j][k][l][m]=min(dp[i][j][k][l-1][m]+1,dp[i][j][k][l][m]);
                        if(k>0) dp[i][j][k][l][m]=min(dp[i][j][k-1][l+1][m]+1,dp[i][j][k][l][m]);
                        if(j>0) dp[i][j][k][l][m]=min(dp[i][j-1][k+1][l][m]+1,dp[i][j][k][l][m]);
                        if(i>0) dp[i][j][k][l][m]=min(dp[i-1][j+1][k][l][m]+1,dp[i][j][k][l][m]);
                        if(k>0) dp[i][j][k][l][m]=min(dp[i][j][k-1][l][m]+1,dp[i][j][k][l][m]);
                        if(j>0) dp[i][j][k][l][m]=min(dp[i][j-1][k][l+1][m]+1,dp[i][j][k][l][m]);
                        if(i>0) dp[i][j][k][l][m]=min(dp[i+1][j][k-1][l][m]+1,dp[i][j][k][l][m]);
                        if(j>0) dp[i][j][k][l][m]=min(dp[i][j-1][k][l][m]+1,dp[i][j][k][l][m]);
                        if(i>0) dp[i][j][k][l][m]=min(dp[i-1][j][k][l+1][m]+1,dp[i][j][k][l][m]);
                        if(j>0&&m>0) dp[i][j][k][l][m]=min(dp[i][j-1][k][l][m-1]+1,dp[i][j][k][l][m]);
                        if(j>0&&l>0) dp[i][j][k][l][m]=min(dp[i][j-1][k][l-1][m]+1,dp[i][j][k][l][m]);
                        if(j>0&&k>0) dp[i][j][k][l][m]=min(dp[i][j-1][k-1][l+1][m]+1,dp[i][j][k][l][m]);
                        if(j>1) dp[i][j][k][l][m]=min(dp[i][j-2][k+1][l][m]+1,dp[i][j][k][l][m]);
                        if(j>0&&i>0) dp[i][j][k][l][m]=min(dp[i-1][j-1+1][k][l][m]+1,dp[i][j][k][l][m]);
                        if(i>0&&l>0) dp[i][j][k][l][m]=min(dp[i-1][j][k][l-1+1][m]+1,dp[i][j][k][l][m]);
                        if(i>0&&k>0) dp[i][j][k][l][m]=min(dp[i-1][j][k-1][l+2][m]+1,dp[i][j][k][l][m]);
                        if(i>0&&j>0) dp[i][j][k][l][m]=min(dp[i-1][j-1][k+1][l+1][m]+1,dp[i][j][k][l][m]);
                        if(i>1) dp[i][j][k][l][m]=min(dp[i-2][j+1][k][l+1][m]+1,dp[i][j][k][l][m]); 
                        if(i>0&&m>0) dp[i][j][k][l][m]=min(dp[i-1][j][k][l+1][m-1]+1,dp[i][j][k][l][m]);
                        if(j>0&&k>0) dp[i][j][k][l][m]=min(dp[i][j-1][k-1][l][m]+1,dp[i][j][k][l][m]);
                        if(j>1) dp[i][j][k][l][m]=min(dp[i][j-2][k][l+1][m]+1,dp[i][j][k][l][m]);
                        if(j>0&&i>0) dp[i][j][k][l][m]=min(dp[i-1][j-1][k+1][l][m]+1,dp[i][j][k][l][m]);
                        if(i>0&&k>0) dp[i][j][k][l][m]=min(dp[i-1][j][k-1][l+1][m]+1,dp[i][j][k][l][m]);
                        if(i>0&&j>0) dp[i][j][k][l][m]=min(dp[i-1][j-1][k][l+2][m]+1,dp[i][j][k][l][m]);
                        if(i>1) dp[i][j][k][l][m]=min(dp[i-2][j][k+1][l+1][m]+1,dp[i][j][k][l][m]);
                        if(i>0&&l>0&&k>0) dp[i][j][k][l][m]=min(dp[i-1][j][k-1][l-1+1][m]+1,dp[i][j][k][l][m]);
                        if(i>0&&l>0&&j>0) dp[i][j][k][l][m]=min(dp[i-1][j-1][k+1][l-1][m]+1,dp[i][j][k][l][m]);
                        if(i>1&&l>0) dp[i][j][k][l][m]=min(dp[i-2][j+1][k][l-1][m]+1,dp[i][j][k][l][m]);
                        if(i>0&&m>1) dp[i][j][k][l][m]=min(dp[i-1][j][k][l][m-2]+1,dp[i][j][k][l][m]);
                        if(i>0&&k>1) dp[i][j][k][l][m]=min(dp[i-1][j][k-2][l+2][m]+1,dp[i][j][k][l][m]);
                        if(i>0&&j>0&&k>0) dp[i][j][k][l][m]=min(dp[i-1][j-1][k-1+1][l+1][m]+1,dp[i][j][k][l][m]);
                        if(i>1&&k>0) dp[i][j][k][l][m]=min(dp[i-2][j+1][k-1][l+1][m]+1,dp[i][j][k][l][m]);
                        if(i>0&&j>1) dp[i][j][k][l][m]=min(dp[i-1][j-2][k+2][l][m]+1,dp[i][j][k][l][m]);
                        if(i>1&&j>0) dp[i][j][k][l][m]=min(dp[i-2][j-1+1][k+1][l][m]+1,dp[i][j][k][l][m]);
                        if(i>2) dp[i][j][k][l][m]=min(dp[i-3][j+2][k][l][m]+1,dp[i][j][k][l][m]);
                        if(i>0&&k>0&&m>0) dp[i][j][k][l][m]=min(dp[i-1][j][k-1][l+1][m-1]+1,dp[i][j][k][l][m]);
                        if(i>0&&j>0&&m>0) dp[i][j][k][l][m]=min(dp[i-1][j-1][k+1][l][m-1]+1,dp[i][j][k][l][m]);
                        if(i>1&&m>0) dp[i][j][k][l][m]=min(dp[i-2][j+1][k][l][m-1]+1,dp[i][j][k][l][m]);
                        if(i>0&&j>0&&k>0) dp[i][j][k][l][m]=min(dp[i-1][j-1][k-1][l+1][m]+1,dp[i][j][k][l][m]);
                        if(i>1&&k>0) dp[i][j][k][l][m]=min(dp[i-2][j][k-1+1][l][m]+1,dp[i][j][k][l][m]);
                        if(i>0&&j>1) dp[i][j][k][l][m]=min(dp[i-1][j-2][k][l+2][m]+1,dp[i][j][k][l][m]);
                        if(i>1&&j>0) dp[i][j][k][l][m]=min(dp[i-2][j-1][k+1][l+1][m]+1,dp[i][j][k][l][m]);
                        if(i>2) dp[i][j][k][l][m]=min(dp[i-3][j][k+2][l][m]+1,dp[i][j][k][l][m]);
                        if(i>0&&k>1) dp[i][j][k][l][m]=min(dp[i-1][j][k-2][l][m]+1,dp[i][j][k][l][m]);
                        if(i>0&&l>1) dp[i][j][k][l][m]=min(dp[i-1][j][k][l-2][m]+1,dp[i][j][k][l][m]);
                        if(i>0&&k>0) dp[i][j][k][l][m]=min(dp[i-1][j][k-1][l][m]+1,dp[i][j][k][l][m]);
                        if(i>1) dp[i][j][k][l][m]=min(dp[i-2][j][k][l][m]+1,dp[i][j][k][l][m]);
                        if(i>0&&l>0&&m>0) dp[i][j][k][l][m]=min(dp[i-1][j][k][l-1][m-1]+1,dp[i][j][k][l][m]);
                        //printf("dp[%d][%d][%d][%d][%d]=%d\n",i,j,k,l,m,dp[i][j][k][l][m]);
                    }
                }
            }
        }
    }   
}
void Search(int now)
{
    for(int i=3;i<=13;i++)
    {
        if(card[i]>=3&&card[i+1]>=3)
        {
            card[i]-=3;card[i+1]-=3;
            Search(now+1);
            int j=i+2;
            while(j<=14&&card[j]>=3)
            {
                card[j]-=3;
                Search(now+1);
                j++;
            }
            for(int k=i;k<j;k++)
            {
                card[k]+=3;
            }
        }
    }
    for(int i=3;i<=12;i++)
    {
        if(card[i]>=2&&card[i+1]>=2&&card[i+2]>=2)
        {
            card[i]-=2;card[i+1]-=2;card[i+2]-=2;
            Search(now+1);
            int j=i+3;
            while(j<=14&&card[j]>=2)
            {
                card[j]-=2;
                Search(now+1);
                j++;
            }
            for(int k=i;k<j;k++)
            {
                card[k]+=2;
            }
        }
    }
    for(int i=3;i<=10;i++)
    {
        if(card[i]>0&&card[i+1]>0&&card[i+2]>0&&card[i+3]>0&&card[i+4]>0)
        {
            card[i]--;card[i+1]--;card[i+2]--;card[i+3]--;card[i+4]--;
            Search(now+1);
            int j=i+5;
            while(j<=14&&card[j]>0)
            {
                card[j]--;
                Search(now+1);
                j++;
            }
            for(int k=i;k<j;k++)
            {
                card[k]++;
            }
        }
    }
    int num4=0,num3=0,num2=0,num1=0,joker=0;
    for(int i=3;i<=15;i++)
    {
        if(card[i]==4) num4++;
        else if(card[i]==3) num3++;
        else if(card[i]==2) num2++;
        else if(card[i]==1) num1++;
    }
    joker=card[16];
    finalans=min(finalans,dp[num4][num3][num2][num1][joker]+now);
    //printf("%d %d %d %d %d %d %d\n",num4,num3,num2,num1,joker,dp[num4][num3][num2][num1][joker]+now,finalans);
}
int main()
{
    //freopen("landlords.in","r",stdin);
    //freopen("landlords.out","w",stdout);
    int x,y;
    T=read();n=read();
    DpBuild();
    while(T--)
    {
        finalans=n;
        memset(card,0,sizeof(card));
        for(int i=1;i<=n;i++)
        {
            x=read();y=read();
            if(x>=3&&x<=13) card[x]++;
            else if(x>=1&&x<=2) card[x+13]++;
            else if(x==0) card[16]++;
        }
        int num4=0,num3=0,num2=0,num1=0,joker=0;
        for(int i=3;i<=15;i++)
        {
            if(card[i]==4) num4++;
            else if(card[i]==3) num3++;
            else if(card[i]==2) num2++;
            else if(card[i]==1) num1++;
        }
        joker=card[16];
        finalans=min(finalans,dp[num4][num3][num2][num1][joker]);
        Search(0);
        printf("%d\n",finalans);
    }
    return 0;
}

0

xianggulinger LV 8 @ 2017-10-21 20:00:51

纯暴力。。。500行。。。简直爆炸。。。

#include <iostream>
using namespace std;
#define For(i, j, k) for(int i = j; i <= k; i++)
int pa[100];
int T;
int n;
int ans = 999999999;
int t;
int fi(){
    For(i, 0, 13){
        if (pa[i] != 0){
            return i;
        }
    }
    return 98765;
}

void s(){
    if (t > ans){
        return;
    }
    int po = fi();

    if (po == 98765){
        ans = min(ans, t);
        return;
    }

    if (po == 0){
        if (pa[po] >= 2){

            pa[po] -= 2;
            t ++;
            s();
            t --;
            pa[po] += 2;
        }
        if (pa[po] >= 1) {

            pa[po] -= 1;
            t ++;
            s();
            t --;
            pa[po] += 1;


            For(j, po + 1, 13){
                if (pa[j] >= 3){
                    pa[j] -= 3;
                    pa[po] --;
                    t ++;
                    s();
                    t --;
                    pa[po] ++;
                    pa[j] += 3;
                }
            }

            For(j, po + 1, 13){
                if (pa[j] >= 4){
                    For(k, po + 1, 13){
                        if (k != j && pa[k] >= 1){
                            pa[j] -= 4;
                            pa[po] --;
                            pa[k] --;
                            t ++;
                            s();
                            t --;
                            pa[k] ++;
                            pa[po] ++;
                            pa[j] += 4;
                        }
                    }
                }
            }
        }

    }

    if (po == 1){
        if (pa[po] >= 4){
            pa[po] -= 4;
            t ++;
            s();
            t --;
            pa[po] += 4;

            For(i, po + 1, 13){
                For(j, i + 1, 13){
                    if (pa[i] >= 1 && pa[j] >= 1){
                        pa[i] -= 1;
                        pa[j] -= 1;
                        pa[po] -= 4;
                        t ++;
                        s();
                        t --;
                        pa[po] += 4;
                        pa[i] += 1;
                        pa[j] += 1;
                    }

                }
            }


            For(i, po + 1, 13){
                For(j, i + 1, 13){
                    if (pa[i] >= 2 && pa[j] >= 2){
                        pa[i] -= 2;
                        pa[j] -= 2;
                        pa[po] -= 4;
                        t ++;
                        s();
                        t --;
                        pa[po] += 4;
                        pa[i] += 2;
                        pa[j] += 2;
                    }

                }
            }
        }
        if (pa[po] >= 3){
            pa[po] -= 3;
            t ++;
            s();
            t --;
            pa[po] += 3;

            For(i, po + 1, 13){
                if (pa[i] >= 1){
                    pa[po] -= 3;
                    pa[i] --;
                    t ++;
                    s();
                    t --;
                    pa[po] += 3;
                    pa[i] ++;
                }
            }

            For(i, po + 1, 13){
                if (pa[i] >= 2){
                    pa[po] -= 3;
                    pa[i] -= 2;
                    t ++;
                    s();
                    t --;
                    pa[po] += 3;
                    pa[i] += 2;
                }
            }



        }
        if (pa[po] >= 2){
            pa[po] -= 2;
            t ++;
            s();
            t --;
            pa[po] += 2;


            For(j, po + 1, 13){
                if (pa[j] >= 4){

                    For(k, po + 1, 13){
                        if (k != j && pa[k] >= 2){

                            pa[j] -= 4;
                            pa[po] -= 2;
                            pa[k] -= 2;
                            t ++;
                            s();
                            t --;
                            pa[k] += 2;
                            pa[po] += 2;
                            pa[j] += 4;
                        }


                    }

                }
            }


            For(j, po + 1, 13){
                if (pa[j] >= 3){
                    pa[j] -= 3;
                    pa[po] -= 2;
                    t ++;
                    s();
                    t --;
                    pa[po] += 2;
                    pa[j] += 3;
                }
            }

        }
        if (pa[po] >= 1){

            For(j, po + 1, 13){
                if (pa[j] >= 3){
                    pa[j] -= 3;
                    pa[po] --;
                    t ++;
                    s();
                    t --;
                    pa[po] ++;
                    pa[j] += 3;
                }
            }

            pa[po] -= 1;
            t ++;
            s();
            t --;
            pa[po] += 1;

            For(j, po + 1, 13){
                if (pa[j] >= 4){

                    For(k, po + 1, 13){
                        if (k != j && pa[k] >= 1){

                            pa[j] -= 4;
                            pa[po] --;
                            pa[k] --;
                            t ++;
                            s();
                            t --;
                            pa[k] ++;
                            pa[po] ++;
                            pa[j] += 4;
                        }


                    }

                }
            }

        }



    }
    if (po >= 2){
        if (pa[po] >= 4){
            pa[po] -= 4;
            t ++;
            s();
            t --;
            pa[po] += 4;

            For(i, po + 1, 13){
                For(j, i + 1, 13){
                    if (pa[i] >= 1 && pa[j] >= 1){
                        pa[i] -= 1;
                        pa[j] -= 1;
                        pa[po] -= 4;
                        t ++;
                        s();
                        t --;
                        pa[po] += 4;
                        pa[i] += 1;
                        pa[j] += 1;
                    }

                }
            }


            For(i, po + 1, 13){
                For(j, i + 1, 13){
                    if (pa[i] >= 2 && pa[j] >= 2){
                        pa[i] -= 2;
                        pa[j] -= 2;
                        pa[po] -= 4;
                        t ++;
                        s();
                        t --;
                        pa[po] += 4;
                        pa[i] += 2;
                        pa[j] += 2;
                    }

                }
            }
        }
        if (pa[po] >= 3){
            pa[po] -= 3;
            t ++;
            s();
            t --;
            pa[po] += 3;

            For(i, po + 1, 13){
                if (pa[i] >= 1){
                    pa[po] -= 3;
                    pa[i] --;
                    t ++;
                    s();
                    t --;
                    pa[po] += 3;
                    pa[i] ++;
                }
            }

            For(i, po + 1, 13){
                if (pa[i] >= 2){
                    pa[po] -= 3;
                    pa[i] -= 2;
                    t ++;
                    s();
                    t --;
                    pa[po] += 3;
                    pa[i] += 2;
                }
            }

            For(j, po + 1, 13){
                if (pa[j] <= 2){
                    break;
                }
                if (j - po + 1 >= 2){
                    For(k, po, j){
                        pa[k] -= 3;
                    }
                    t++;
                    s();
                    t--;
                    For(k, po, j){
                        pa[k] += 3;
                    }
                }
            }
        }
        if (pa[po] >= 2){
            pa[po] -= 2;
            t ++;
            s();
            t --;
            pa[po] += 2;

            For(j, po + 1, 13){
                if (pa[j] <= 1){
                    break;
                }
                if (j - po + 1 >= 3){
                    For(k, po, j){
                        pa[k] -= 2;
                    }
                    t++;
                    s();
                    t--;
                    For(k, po, j){
                        pa[k] += 2;
                    }
                }
            }


            For(j, po + 1, 13){
                if (pa[j] >= 4){

                    For(k, po + 1, 13){
                        if (k != j && pa[k] >= 2){

                            pa[j] -= 4;
                            pa[po] -= 2;
                            pa[k] -= 2;
                            t ++;
                            s();
                            t --;
                            pa[k] += 2;
                            pa[po] += 2;
                            pa[j] += 4;
                        }


                    }

                }
            }


            For(j, po + 1, 13){
                if (pa[j] >= 3){
                    pa[j] -= 3;
                    pa[po] -= 2;
                    t ++;
                    s();
                    t --;
                    pa[po] += 2;
                    pa[j] += 3;
                }
            }

        }
        if (pa[po] >= 1){
            pa[po] -= 1;
            t ++;
            s();
            t --;
            pa[po] += 1;

            For(j, po + 1, 13){
                if (pa[j] >= 3){
                    pa[j] -= 3;
                    pa[po] --;
                    t ++;
                    s();
                    t --;
                    pa[po] ++;
                    pa[j] += 3;
                }
            }

            For(j, po + 1, 13){
                if (pa[j] >= 4){

                    For(k, po + 1, 13){
                        if (k != j && pa[k] >= 1){

                            pa[j] -= 4;
                            pa[po] --;
                            pa[k] --;
                            t ++;
                            s();
                            t --;
                            pa[k] ++;
                            pa[po] ++;
                            pa[j] += 4;
                        }


                    }

                }
            }

            For(j, po + 1, 13){
                if (pa[j] == 0){
                    break;
                }
                if (j - po + 1 >= 5){
                    For(k, po, j){
                        pa[k] --;
                    }
                    t++;
                    s();
                    t--;
                    For(k, po, j){
                        pa[k] ++;
                    }}
            }
        }
    }


}
int main(){
//  freopen("landlords.in", "r", stdin);
//  freopen("landlords.out", "w", stdout);
    cin >> T >> n;

    For(dhias, 1, T){
        For(i, 0, 99){
            pa[i] = 0;
        }
        t = 0;
        ans = 999999999;
        int tjo, tch;
        For(i, 1, n){
            cin >> tjo >> tch;
            if (3 <= tjo && tjo <= 13){
                pa[tjo - 1]++;
            }
            if (tjo == 0){
                pa[0] ++;
            }
            if (tjo == 1){
                pa[13] ++;
            }
            if (tjo == 2){
                pa[1] ++;
            }
        }
        s();
        cout << ans << endl;
    }
    return 0;
}

0

Ximenbao LV 8 @ 2017-10-20 13:25:04

先预处理不打顺子的情况：记下有c1种1张的数码，c2种2张的数码，c3种3张的数码，c4种4张的数码时打光所有牌需要的最小次数。然后DFS搜索已经打过顺子的所有可能情况。
最坑爹的是俩王不能被带...还要加个特判。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[24][13][9][7];
int dfs(int c1,int c2,int c3,int c4)
{
    if(f[c1][c2][c3][c4]>-1)   return f[c1][c2][c3][c4];
    if(!(c1||c2||c3||c4))   return f[c1][c2][c3][c4]=0;
    int ans=1e9;
    if(c4>0)
    {
        if(c2>1)   ans=min(ans,dfs(c1,c2-2,c3,c4-1));
        if(c1>1)   ans=min(ans,dfs(c1-2,c2,c3,c4-1));
        ans=min(ans,dfs(c1,c2,c3,c4-1));
    }
    if(c3>0)
    {
        if(c2>0)   ans=min(ans,dfs(c1,c2-1,c3-1,c4));
        if(c1>0)   ans=min(ans,dfs(c1-1,c2,c3-1,c4));
        ans=min(ans,dfs(c1,c2,c3-1,c4));
    }
    if(c2>0)   ans=min(ans,dfs(c1,c2-1,c3,c4));
    if(c1>0)   ans=min(ans,dfs(c1-1,c2,c3,c4));
    return f[c1][c2][c3][c4]=ans+1;
}
int DFS(int A[])
{
    int C[5]; //有i张的有几个
    bool B[15][5]; //i号牌是否有j张
    memset(B,0,sizeof(B));
    memset(C,0,sizeof(C));//init.
    for(int i=0;i<=13;i++)
        for(int j=1;j<=A[i];j++)
        {
            B[i][j]=1;//i号牌有j张
            if(i==1)   B[14][j]=1;//A放到K后面
        }
    for(int i=0;i<=13;i++)   C[A[i]]++;//1234张的号码的数量
    int ans=dfs(C[1],C[2],C[3],C[4]); //不考虑顺子
    int last=0,shunzi[4]={0,5,3,2};//顺子起始,顺子张数
    for(int j=3;j>0;j--)//123连顺
    {
        last=0;
        for(int i=3;i<=14;i++)//搜3~A(14)
        {
            if(B[i][j]&&(last==0))   last=i;//i号有j张,则记录顺子起始
            if(B[i][j]&&last>0&&((i-last+1)>=shunzi[j])) 
              //顺子已有shunzi[j]张以上
            {
                int tA[14];
                for(int t=0;i-last-t+1>=shunzi[j];t++)
                {
                    for(int k=0;k<=13;k++)   tA[k]=A[k];
                    for(int k=last+t;k<=i;k++)
                    {
                        if(k==14)   tA[1]=A[1]-j;
                        else   tA[k]=A[k]-j;
                    }//新的方案
                    ans=min(ans,1+DFS(tA));
                }
            }
            if(!B[i][j])   last=0;//要断
        }
    }
    return ans;
}
int main()
{
    int x,n;
    scanf("%d%d",&x,&n);
    memset(f,-1,sizeof(f));
    for(int c1=0;c1<=23;c1++)
       for(int c2=0;c2<=12;c2++)
          for(int c3=0;c3<=8;c3++)
             for(int c4=0;c4<=6;c4++)
                 dfs(c1,c2,c3,c4);
    //初始化:对于每一种张数的号码的数量,不打顺子的最小值
    while(x--)
    {
        int A[14],anti_kengdie=0;//i点的张数
        memset(A,0,sizeof(A));
        for(int i=1;i<=n;i++)
        {
            int num,d;
            scanf("%d%d",&num,&d);
            A[num]++;//num点的牌共几张
        }
        if(A[0]==2)
        {
            A[0]=0;
            anti_kengdie=1;
        }
        printf("%d\n",anti_kengdie+DFS(A));
    }
    return 0;
}

0

Ximenbao LV 8 @ 2017-10-20 07:28:39

先初始化不打顺子的情形，f[c1][c2][c3][c4]表示ci点的牌有i张时，打完需要的最少次数
之后dfs搜索打完若干顺子后的所有可能情况。
注意俩猫不能被三、四带走...坑爹呢这是
cpp #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int f[24][13][9][7]; int dfs(int c1,int c2,int c3,int c4) { if(f[c1][c2][c3][c4]>-1) return f[c1][c2][c3][c4]; if(!(c1||c2||c3||c4)) return f[c1][c2][c3][c4]=0; int ans=1e9; if(c4>0) { if(c2>1) ans=min(ans,dfs(c1,c2-2,c3,c4-1)); if(c1>1) ans=min(ans,dfs(c1-2,c2,c3,c4-1)); ans=min(ans,dfs(c1,c2,c3,c4-1)); } if(c3>0) { if(c2>0) ans=min(ans,dfs(c1,c2-1,c3-1,c4)); if(c1>0) ans=min(ans,dfs(c1-1,c2,c3-1,c4)); ans=min(ans,dfs(c1,c2,c3-1,c4)); } if(c2>0) ans=min(ans,dfs(c1,c2-1,c3,c4)); if(c1>0) ans=min(ans,dfs(c1-1,c2,c3,c4)); return f[c1][c2][c3][c4]=ans+1; } int DFS(int A[]) { int C[5]; //有i张的有几个 bool B[15][5]; //i号牌是否有j张 memset(B,0,sizeof(B)); memset(C,0,sizeof(C));//init. for(int i=0;i<=13;i++) for(int j=1;j<=A[i];j++) { B[i][j]=1;//i号牌有j张 if(i==1) B[14][j]=1;//A放到K后面 } for(int i=0;i<=13;i++) C[A[i]]++;//1234张的号码的数量 int ans=dfs(C[1],C[2],C[3],C[4]); //不考虑顺子 int last=0,shunzi[4]={0,5,3,2};//顺子起始,顺子张数 for(int j=3;j>0;j--)//123连顺 { last=0; for(int i=3;i<=14;i++)//搜3~A(14) { if(B[i][j]&&(last==0)) last=i;//i号有j张,则记录顺子起始 if(B[i][j]&&last>0&&((i-last+1)>=shunzi[j])) //顺子已有shunzi[j]张以上 { int tA[14]; for(int t=0;i-last-t+1>=shunzi[j];t++) { for(int k=0;k<=13;k++) tA[k]=A[k]; for(int k=last+t;k<=i;k++) { if(k==14) tA[1]=A[1]-j; else tA[k]=A[k]-j; }//新的方案 ans=min(ans,1+DFS(tA)); } } if(!B[i][j]) last=0;//顺子断 } } return ans; } int main() { int x,n; scanf("%d%d",&x,&n); memset(f,-1,sizeof(f)); for(int c1=0;c1<=23;c1++) for(int c2=0;c2<=12;c2++) for(int c3=0;c3<=8;c3++) for(int c4=0;c4<=6;c4++) dfs(c1,c2,c3,c4); //初始化:对于每一种张数的牌的数量,不打顺子出完的最小次数 while(x--) { int A[14],anti_kengdie=0;//i点的张数及防止俩猫不能带的坑爹 memset(A,0,sizeof(A)); for(int i=1;i<=n;i++) { int num,d; scanf("%d%d",&num,&d); A[num]++;//num点的牌共几张 } if(A[0]==2) { A[0]=0; anti_kengdie=1; } printf("%d\n",anti_kengdie+DFS(A)); } return 0; }

0

foreverpiano LV 8 @ 2017-08-27 19:25:49

有人知道为什么会wa在95个点吗

#include<bits/stdc++.h>
#define cls(a,b) memset(a,b,sizeof(a))
using namespace std;
int B[5]={0,4,2,1};
int cnt[110],sum[110],n,t,ans=0;
int C() {
    #define RP(a,b,c,d) while(cnt[a]>=b&&cnt[c]>=d) cnt[a]-=b,cnt[c]-=d,res++
    cls(cnt,0);for(int i=1;i<=14;i++) cnt[sum[i]]++;int res=0;
    RP(4,1,2,2);RP(4,1,1,2);RP(3,1,2,1);RP(3,1,1,1);return res+cnt[1]+cnt[2]+cnt[3]+cnt[4];
}
void dfs(int S) {
    if(S>ans) return ;ans=min(ans,C()+S);int i,j,k,t,c;
    for(t=3;t>=1;t--) 
        for(i=3,j;i<=14;i++) {
            for(j=i;sum[j]>=t;j++);
            for(j--,k=i+B[t];k<=j;k++) {
                for(c=i;c<=k;c++) sum[c]-=t;
                dfs(S+1);
                for(c=i;c<=k;c++) sum[c]+=t;
            }
        }
    if(sum[1]==2) sum[1]=0,dfs(S+1),sum[1]=2;
}
main() {
    cin>>t>>n;
    for(;t;t--) {
        cls(sum,0);ans=0;
        for(int i=1,a,b;i<=n;i++) {
            scanf("%d%d",&a,&b);
            if(a==1) a=14;else if(!a) a++;
            sum[a]++;
        }
        ans=C();dfs(0);cout<<ans<<"\n";
    }
}

奕sir @ 2017-11-09 20:29:40

双王不能当对子处理

0

独孤无影手andy LV 8 @ 2017-07-26 21:24:52

对于这题，我对于出了这100个数据的大佬只能说是佩服透了、跪烂了！
话说我在99分那里死了很久，然后发现网上好多的所谓的AC代码也是99的~
无语无语
然后看了楼下的一位大佬，才发现一个东西：
#王炸#
🚀火箭🚀是不能放在三带二里面的，不过题目好像没说……（可能是我没看见）
其实我还是觉得奇怪：比如现在只剩下3组炸弹了，照大多数标算的（包括我的），这样要3次，
but其实来2次4带2就可以解决……不知道是否有人能给我答案（期待）
这题是这样做的：
1. 对于顺子，dfs 按照3顺子、2顺子、1顺子顺序来（可能会快一点）
2. 对于每种剩余的牌的情况，不管还能不能打出顺子，我们统计一下剩余的不打顺子最少几个，是可以不通过搜索直接解决的（但我还是不大理解），用这个答案来更新结果；
3. 剪枝： if (now>=ans) return;

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
const int P=20;
// Three are totally 14 kinds of cards ：0~13 
int p[P],T,n,ans;
int restep(){
    int c[5],step=0/*,s1,s2*/;
    memset(c,0,sizeof c);
    for (int i=0;i<=13;i++)
        c[p[i]]++;
    if (p[0]==2){
        if (c[4]>=1&&c[2]>=2)
            c[4]-=1,c[2]-=2,step++;
        else if (c[4]>=1&&c[2]>=1)
            c[4]-=1,c[2]-=1,step++;
        else
            c[2]-=1,step++;
    }
    while (c[4]>=1&&c[1]>=2)c[4]-=1,c[1]-=2,step++;
    while (c[4]>=1&&c[2]>=2)c[4]-=1,c[2]-=2,step++;
    while (c[4]>=1&&c[2]>=1)c[4]-=1,c[2]-=1,step++;
    while (c[3]>=1&&c[2]>=1)c[3]-=1,c[2]-=1,step++;
    while (c[3]>=1&&c[1]>=1)c[3]-=1,c[1]-=1,step++;
    return step+c[1]+c[2]+c[3]+c[4];
}
void dfs(int now){
    int le,ri,L=2,R=14;
    if (now>=ans)
        return;
    int step=restep();
    if (ans>now+step)
        ans=now+step;
    //三顺子 
    for (le=L;le<R;le++){
        ri=le;
        while (ri<R&&p[ri]>=3)
            ri++;
        if (ri-le>=2)
            for (int x=le+2;x<=ri;x++){
                for (int i=le;i<x;i++)
                    p[i]-=3;
                dfs(now+1);
                for (int i=le;i<x;i++)
                    p[i]+=3;
            }
    }
    //三顺子 
    //双顺子 
    for (le=L;le<R;le++){
        ri=le;
        while (ri<R&&p[ri]>=2)
            ri++;
        if (ri-le>=3)
            for (int x=le+3;x<=ri;x++){
                for (int i=le;i<x;i++)
                    p[i]-=2;
                dfs(now+1);
                for (int i=le;i<x;i++)
                    p[i]+=2;
            }
    }
    //双顺子 
    //单顺子 
    for (le=L;le<R;le++){
        ri=le;
        while (ri<R&&p[ri]>=1)
            ri++;
        if (ri-le>=5)
            for (int x=le+5;x<=ri;x++){
                for (int i=le;i<x;i++)
                    p[i]-=1;
                dfs(now+1);
                for (int i=le;i<x;i++)
                    p[i]+=1;
            }
    }
    //单顺子 
}
int main(){
    scanf("%d%d",&T,&n);
    while (T--){
        memset(p,0,sizeof p);
        for (int i=1,a,b;i<=n;i++){
            scanf("%d%d",&a,&b);
            if (a==1)
                a=13;
            else if (a>0)
                a--;
            p[a]++;
        }
        ans=n;
        dfs(0);
        printf("%d\n",ans);
    }
    return 0;
}

913846365 @ 2017-08-16 12:40:54

三个炸弹不可以两次四带二，因为必须是两张不同的单牌或两对不同的对子

0

wuwangmao LV 8 @ 2016-11-17 22:39:13

http://www.cnblogs.com/zbtrs/p/5766051.html

0

阿波罗 LV 8 @ 2016-10-17 15:45:52

搜顺子，然后计算对子和带牌
```c++

#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<algorithm>
#define smin(a, b) a = min(a, b)
using namespace std;
typedef bool boolean;
template<typename T>
inline void readInteger(T& u){
char x;
while(!isdigit((x = getchar())));
for(u = x - '0'; isdigit((x = getchar())); u = (u << 3) + (u << 1) + x - '0');
ungetc(x, stdin);
}

int n;
int kase;
int key[14] = {0, 12, 13, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
int had[16];

inline void init(){
memset(had, 0, sizeof(had));
for(int i = 1, a, b; i <= n; i++){
readInteger(a);
readInteger(b);
if(a == 0) had[13 + b]++;
else had[key[a]]++;
}
}

int calc(){
int counter[5] = {0, 0, 0, 0, 0};
for(int i = 1; i <= 15; i++){
if(had[i] > 0){
counter[had[i]]++;
}
}
int reter = 0;
boolean aFlag = 0;
if(had[14] == 1 && had[15] == 1){

aFlag = 1;
}
while(counter[4] && counter[2] >= 2) reter++, counter[4] -= 1, counter[2] -= 2;
while(counter[4] && counter[1] >= 2) reter++, counter[4] -= 1, counter[1] -= 2;
while(counter[4] && counter[2]) reter++, counter[4] -= 1, counter[2] -= 1;
while(counter[3] && counter[2]) reter++, counter[3] -= 1, counter[2] -= 1;
while(counter[3] && counter[1]) reter++, counter[3] -= 1, counter[1] -= 1;
if(counter[1] >= 2 && aFlag) counter[1] -= 1;
return reter + counter[1] + counter[2] + counter[3] + counter[4];
}

int result;
void search(int last, int times){
if(last == 0){
smin(result, times);
return;
}
smin(result, times + calc());
if(times >= result) return;
//顺子
if(last >= 5){
for(int p = 3; p >= 1; p--){
for(int i = 1; i <= 12; i++){
int k = i;
while(had[k] >= p && k < 13) k++;
if((k - i) * p >= 5){
for(int j = i; j < k; j++){
had[j] -= p;
}
for(int j = k - 1; j >= i; j--){
if((j - i + 1) * p >= 5)
search(last - (j - i + 1) * p, times + 1);
had[j] += p;
}
}

}
}
}
}

int main(){
readInteger(kase);
readInteger(n);
while(kase--){
init();
result = n;
search(n, 0);
printf("%d\n", result);
}
return 0;
}
```

0

explodingnerk LV 8 @ 2016-10-10 21:42:48

在ccz大爷的帮助下终于知道了ta[]tb[]会改变。。。见识了大爷的各种神乎其神的调试技巧。。。跪烂了跪烂了。。。
然后这份暴力+剪枝的代码vijos上96.官方数据95.嗯其他的都是WA不想理了ＴＡＴ
#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> #include<algorithm> using namespace std; #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define clr(x,c) memset(x,c,sizeof(x)) int read(){ int x=0,f=1;char c=getchar(); while(!isdigit(c)){ if(c=='-') f=-1;c=getchar(); } while(isdigit(c)) x=x*10+c-'0',c=getchar(); return x*f; } const int nmax=25; const int inf=0x7f7f7f7f; int a[nmax],ans,cnt=0; void mins(int &a,int b){ if(a>b) a=b; } void dfs(int tmp){ if(tmp>=ans) return ; int cnt=0; rep(i,2,14) if(a[i]) cnt++; mins(ans,tmp+cnt); if(!cnt) return ; int ta[nmax]={0},tb[nmax]={0}; rep(i,3,10){ int cur=0; rep(j,i,14) if(!a[j]) { cur=j;break; } if(!cur) cur=15;--cur; if(cur-i+1>=5) { rep(j,i,i+3) a[j]--; rep(j,i+4,cur) a[j]--,dfs(tmp+1); rep(j,i,cur) a[j]++; } } rep(i,3,12){ int cur=0; rep(j,i,14) if(a[j]<2){ cur=j;break; } if(!cur) cur=15;--cur; if(cur-i+1>=3){ rep(j,i,i+1) a[j]-=2; rep(j,i+2,cur) a[j]-=2,dfs(tmp+1); rep(j,i,cur) a[j]+=2; } } rep(i,3,13){ int cur=0; rep(j,i,14) if(a[j]<3){ cur=j;break; } if(!cur) cur=15;--cur; if(cur-i+1>=2){ a[i]-=3; rep(j,i+1,cur) a[j]-=3,dfs(tmp+1); rep(j,i,cur) a[j]+=3; } } rep(i,2,14){ if(a[i]>=3){ int ca=0,cb=0; rep(j,2,14) if(j!=i&&a[j]>=2) ta[++ca]=j; rep(j,2,14) if(j!=i&&a[j]>=1) tb[++cb]=j; a[i]-=3; rep(j,1,ca){ a[ta[j]]-=2;dfs(tmp+1);a[ta[j]]+=2; } rep(j,1,cb) { a[tb[j]]--;dfs(tmp+1);a[tb[j]]++; } a[i]+=3; if(a[i]==4){ a[i]-=4; rep(j,1,ca-1) rep(k,j+1,ca) { a[ta[j]]-=2;a[ta[k]]-=2; dfs(tmp+1);a[ta[j]]+=2;a[ta[k]]+=2; } rep(j,1,cb-1) rep(k,j+1,cb) { a[tb[j]]--;a[tb[k]]--; dfs(tmp+1);a[tb[j]]++;a[tb[k]]++; } rep(j,1,ca){ a[ta[j]]-=2;dfs(tmp+1);a[ta[j]]+=2; } a[i]+=4; } } } return ; } int main(){ freopen("landlords.in","r",stdin); freopen("landlords.ans","w",stdout); int T=read(),n=read(); while(T--){ int u,v,d;ans=inf;clr(a,0); rep(i,1,n) { u=read(),v=read(); if(u==0&&v==1) u=16; else if(u==0&&v==2) u=15; else if(u==1) u=14; a[u]++; } dfs(0); if(a[16]||a[15]) ans++; printf("%d\n",ans); } return 0; }

0

liuyiah LV 10 @ 2016-09-10 11:02:39

提一点，顺子会影响出牌次数，如果忽略顺子不打，那么最少出牌次数是一定的。
这样DFS都可以过了，用不上DP

0

846047746 LV 7 @ 2016-08-11 11:45:17

先预处理dp出打光i个4张码数相同的牌、j个3张码数相同的牌、k个2张码数相同的牌和l张单牌所需要的最少步数，再dfs顺子，结合预处理得出答案（PS：大小王要特判什么的，不能当对子用）

评测结果
测试数据 #0: Accepted, time = 15 ms, mem = 660 KiB, score = 1
测试数据 #1: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #2: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #3: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #4: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #5: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #6: Accepted, time = 15 ms, mem = 656 KiB, score = 1
测试数据 #7: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #8: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #9: Accepted, time = 0 ms, mem = 664 KiB, score = 1
测试数据 #10: Accepted, time = 15 ms, mem = 660 KiB, score = 1
测试数据 #11: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #12: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #13: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #14: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #15: Accepted, time = 0 ms, mem = 664 KiB, score = 1
测试数据 #16: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #17: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #18: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #19: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #20: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #21: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #22: Accepted, time = 0 ms, mem = 664 KiB, score = 1
测试数据 #23: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #24: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #25: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #26: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #27: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #28: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #29: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #30: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #31: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #32: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #33: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #34: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #35: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #36: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #37: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #38: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #39: Accepted, time = 15 ms, mem = 660 KiB, score = 1
测试数据 #40: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #41: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #42: Accepted, time = 15 ms, mem = 660 KiB, score = 1
测试数据 #43: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #44: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #45: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #46: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #47: Accepted, time = 15 ms, mem = 660 KiB, score = 1
测试数据 #48: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #49: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #50: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #51: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #52: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #53: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #54: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #55: Accepted, time = 15 ms, mem = 660 KiB, score = 1
测试数据 #56: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #57: Accepted, time = 15 ms, mem = 660 KiB, score = 1
测试数据 #58: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #59: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #60: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #61: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #62: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #63: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #64: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #65: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #66: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #67: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #68: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #69: Accepted, time = 15 ms, mem = 660 KiB, score = 1
测试数据 #70: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #71: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #72: Accepted, time = 15 ms, mem = 660 KiB, score = 1
测试数据 #73: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #74: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #75: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #76: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #77: Accepted, time = 15 ms, mem = 656 KiB, score = 1
测试数据 #78: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #79: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #80: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #81: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #82: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #83: Accepted, time = 15 ms, mem = 660 KiB, score = 1
测试数据 #84: Accepted, time = 15 ms, mem = 660 KiB, score = 1
测试数据 #85: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #86: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #87: Accepted, time = 15 ms, mem = 656 KiB, score = 1
测试数据 #88: Accepted, time = 15 ms, mem = 660 KiB, score = 1
测试数据 #89: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #90: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #91: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #92: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #93: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #94: Accepted, time = 0 ms, mem = 664 KiB, score = 1
测试数据 #95: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #96: Accepted, time = 15 ms, mem = 660 KiB, score = 1
测试数据 #97: Accepted, time = 0 ms, mem = 660 KiB, score = 1
测试数据 #98: Accepted, time = 0 ms, mem = 656 KiB, score = 1
测试数据 #99: Accepted, time = 0 ms, mem = 656 KiB, score = 1
Accepted, time = 240 ms, mem = 664 KiB, score = 100

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iostream>
int f[6][10][16][28],s[14],num[5],m,n,ans,temp;
inline int read()
{
    int c=getchar(),t=0;
    for(;c<48||57<c;c=getchar());
    do
    {
        t=(t<<3)+(t<<1)+c-48;
        c=getchar();
    }while(48<=c&&c<=57);
    return t;
}
inline int min(int x,int y) {x-=y;return y+(x&(x>>31));}
inline void dfs(int x)
{
    if(x>=ans) return;
    memset(num,0,sizeof(num));
    num[1]+=s[0];for(int i=1;i<=13;++i) ++num[s[i]];
    ans=min(ans,x+f[num[4]][num[3]][num[2]][num[1]]);
    for(int i=12,j;i>=5;--i)
    {
        for(j=i;j+3>=i&&s[j]>=1;--j) --s[j];
        if(j+3<i) for(;j&&s[j]>=1;--j) --s[j],dfs(x+1);
        for(int k=i;k>j;--k) ++s[k];
    }
    for(int i=12,j;i>=3;--i)
    {
        if(s[i]>=2&&s[i-1]>=2)
        {
            for(s[i]-=2,s[i-1]-=2,j=i-2;j&&s[j]>=2;--j) s[j]-=2,dfs(x+1);
            for(int k=i;k>j;--k) s[k]+=2;
        }
    }
    for(int i=12,j;i>=2;--i)
    {
        if(s[i]>=3)
        {
            for(s[i]-=3,j=i-1;j&&s[j]>=3;--j) s[j]-=3,dfs(x+1);
            for(int k=i;k>j;--k) s[k]+=3;
        }
    }
    if(s[0]==2) s[0]=0,dfs(x+1),s[0]=2;
}
int main()
{
    m=read();n=read();
    memset(f,127,sizeof(f));
    f[0][0][0][0]=-1;
    for(int i=0;i<=5;++i)
    for(int j=0;j<=8;++j)
    for(int k=0;k<=13;++k)
    for(int l=0;l<=25;++l)
    {
        int &F=f[i][j][k][l];
        if(i>=1&&k>=2) F=min(F,f[i-1][j][k-2][l]);
        if(i>=1&&l>=2) F=min(F,f[i-1][j][k][l-2]);
        if(i>=1) F=min(F,f[i-1][j][k][l]);
        if(j>=1&&k>=1) F=min(F,f[i][j-1][k-1][l]);
        if(j>=1&&l>=1) F=min(F,f[i][j-1][k][l-1]);
        if(j>=1) F=min(F,f[i][j-1][k][l]);
        if(k>=1) F=min(F,f[i][j][k-1][l]);
        if(l>=1) F=min(F,f[i][j][k][l-1]);
        ++F;
        if(i>=1) F=min(F,min(f[i-1][j+1][k][l+1],f[i-1][j][k+2][l]));
        if(j>=1) F=min(F,f[i][j-1][k+1][l+1]);
        if(k>=1) F=min(F,f[i][j][k-1][l+2]);
    }
    while(m--)
    {
        memset(s,0,sizeof(s));ans=23;
        for(int i=1;i<=n;++i,read())
        {
            temp=read();
            if(temp==0) ++s[0];
            else ++s[(temp+10)%13+1];
        }
        dfs(0);
        printf("%d\n",ans);
    }
}```

0

沙滩玉米 LV 8 @ 2016-04-02 21:50:26

贴一段pascal的代码，基本思想是dfs+一点贪心思想（数据处理上有点复杂）
var
n,t,x,y,i,ans:longint;
a:array[0..15] of longint;
p:array[0..4] of longint;
toe:array[1..3] of longint=(5,3,2);
procedure dfs(an:longint);
var i,j:longint;
begin
if an>=ans then exit;j:=0;
for i:=1 to 4 do j:=j+p[i];
if j+an<ans then ans:=j+an;
if p[4]>0 then begin
dec(p[4]);
for i:=4 downto 2 do if p[i]>0 then begin
dec(p[i]);inc(p[i-2]);
for j:=2 to 4 do
if p[j]>0 then begin
dec(p[j]);inc(p[j-2]);
dfs(an+1);
inc(p[j]);dec(p[j-2]);
end;
inc(p[i]);dec(p[i-2]);
end;
for i:=1 to 4 do if p[i]>0 then begin
dec(p[i]);inc(p[i-1]);
for j:=1 to 4 do
if p[j]>0 then begin
dec(p[j]);inc(p[j-1]);
dfs(an+1);
inc(p[j]);dec(p[j-1]);
end;
inc(p[i]);dec(p[i-1]);
end;
i:=i;
inc(p[4]);
end;
if p[3]>0 then begin
dec(p[3]);
for i:=2 to 4 do if p[i]>0 then begin
dec(p[i]);inc(p[i-2]);dfs(an+1);inc(p[i]);dec(p[i-2]);
end;
for i:=1 to 4 do if p[i]>0 then begin
dec(p[i]);inc(p[i-1]);dfs(an+1);inc(p[i]);dec(p[i-1]);
end;
inc(p[3]);
end;
end;
procedure solve(an:longint);
var i,j,k,jj:longint;
begin
if an>=ans then exit;
fillchar(p,sizeof(p),0);
for i:=1 to 15 do inc(p[a[i]]);
if p[0]=15 then begin
ans:=an;exit;
end;
dfs(an);
for k:=1 to 3 do begin
for i:=1 to 14-toe[k]-1 do
if a[i]>=k then begin
for j:=i+1 to 12 do
if a[j]<k then break;
if a[j]<k then dec(j);
if j-i+1<toe[k] then continue;jj:=j;
for j:=i to i+toe[k]-1 do dec(a[j],k);
solve(an+1);
for j:=i+toe[k] to jj do begin
dec(a[j],k);
solve(an+1);
end;
for j:=i to jj do inc(a[j],k);
end;
i:=i;
end;
end;
begin
readln(t,n);
for t:=1 to t do begin
ans:=13;
fillchar(a,sizeof(a),0);
for i:=1 to n do begin
readln(x,y);
if (x>=3)and(x<=13) then inc(a[x-2])
else if x=1 then inc(a[12])
else if x=2 then inc(a[13])
else if y=1 then inc(a[14]) else inc(a[15]);
end;
if (a[14]>0)and(a[15]>0) then begin
a[14]:=0;a[15]:=0;
solve(1);
a[14]:=1;a[15]:=1;
end;
solve(0);
writeln(ans);
end;
end.

0

TenderRun LV 10 @ 2016-03-09 18:09:57

测试数据 #0: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #1: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #2: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #3: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #4: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #5: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #6: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #7: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #8: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #9: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #10: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #11: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #12: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #13: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #14: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #15: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #16: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #17: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #18: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #19: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #20: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #21: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #22: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #23: Accepted, time = 0 ms, mem = 2516 KiB, score = 1

测试数据 #24: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

测试数据 #25: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #26: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #27: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #28: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #29: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #30: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

测试数据 #31: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

测试数据 #32: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #33: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

测试数据 #34: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #35: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

测试数据 #36: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

测试数据 #37: Accepted, time = 15 ms, mem = 2516 KiB, score = 1

测试数据 #38: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

测试数据 #39: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #40: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #41: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

测试数据 #42: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #43: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #44: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

测试数据 #45: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #46: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #47: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #48: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

测试数据 #49: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

测试数据 #50: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

测试数据 #51: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

测试数据 #52: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

测试数据 #53: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

测试数据 #54: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

测试数据 #55: Accepted, time = 31 ms, mem = 2512 KiB, score = 1

测试数据 #56: Accepted, time = 31 ms, mem = 2508 KiB, score = 1

测试数据 #57: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

测试数据 #58: Accepted, time = 15 ms, mem = 2516 KiB, score = 1

测试数据 #59: Accepted, time = 31 ms, mem = 2512 KiB, score = 1

测试数据 #60: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

测试数据 #61: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #62: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #63: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #64: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #65: Accepted, time = 0 ms, mem = 2512 KiB, score = 1

测试数据 #66: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #67: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

测试数据 #68: Accepted, time = 0 ms, mem = 2508 KiB, score = 1

测试数据 #69: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

测试数据 #70: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

测试数据 #71: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

测试数据 #72: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

测试数据 #73: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

测试数据 #74: Accepted, time = 15 ms, mem = 2512 KiB, score = 1

测试数据 #75: Accepted, time = 234 ms, mem = 2508 KiB, score = 1

测试数据 #76: Accepted, time = 46 ms, mem = 2508 KiB, score = 1

测试数据 #77: Accepted, time = 109 ms, mem = 2508 KiB, score = 1

测试数据 #78: Accepted, time = 31 ms, mem = 2508 KiB, score = 1

测试数据 #79: Accepted, time = 15 ms, mem = 2508 KiB, score = 1

测试数据 #80: Accepted, time = 93 ms, mem = 2512 KiB, score = 1

测试数据 #81: Accepted, time = 62 ms, mem = 2512 KiB, score = 1

测试数据 #82: Accepted, time = 125 ms, mem = 2512 KiB, score = 1

测试数据 #83: Accepted, time = 46 ms, mem = 2508 KiB, score = 1

测试数据 #84: Accepted, time = 46 ms, mem = 2508 KiB, score = 1

测试数据 #85: Accepted, time = 218 ms, mem = 2508 KiB, score = 1

测试数据 #86: Accepted, time = 187 ms, mem = 2508 KiB, score = 1

测试数据 #87: Accepted, time = 156 ms, mem = 2512 KiB, score = 1

测试数据 #88: Accepted, time = 453 ms, mem = 2512 KiB, score = 1

测试数据 #89: Accepted, time = 187 ms, mem = 2512 KiB, score = 1

测试数据 #90: Accepted, time = 578 ms, mem = 2508 KiB, score = 1

测试数据 #91: Accepted, time = 703 ms, mem = 2512 KiB, score = 1

测试数据 #92: Accepted, time = 765 ms, mem = 2512 KiB, score = 1

测试数据 #93: Accepted, time = 109 ms, mem = 2508 KiB, score = 1

测试数据 #94: Accepted, time = 328 ms, mem = 2508 KiB, score = 1

测试数据 #95: Accepted, time = 265 ms, mem = 2508 KiB, score = 1

测试数据 #96: Accepted, time = 359 ms, mem = 2508 KiB, score = 1

测试数据 #97: Accepted, time = 421 ms, mem = 2512 KiB, score = 1

测试数据 #98: WrongAnswer, time = 359 ms, mem = 2508 KiB, score = 0

测试数据 #99: WrongAnswer, time = 546 ms, mem = 2512 KiB, score = 0

0

TenderRun LV 10 @ 2016-02-27 15:09:35

dancing link 可做吗

0

xmyjd LV 8 @ 2016-01-09 04:25:44

注意:题意的重点.
2个王一般情况是不视作1对的.火箭不是对.
4带2,可以带2个王.
3带2,不可以带2个王.
但是3带1,可以带1个王.

0

feng_lingsong LV 9 @ 2015-12-20 14:39:17

memset有毒！！写了两个个多余的memset并且数组开大了8倍才40分，去掉了之后并且数组开小了一点就AC了......
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define rep(i, x, y) for (int i = x; i <= y; ++i)
#define dwn(i, x, y) for (int i = x; i >= y; --i)
#define pu {temp = encode(tot); if (!vis[temp]) {vis[temp] = true; q[++tl] = temp; dist[tl] = dist[hd] + 1;}}
#define INF 1 << 30

using namespace std;

const int maxs = 1 << 20;
int T, n;
int vis[maxs], dist[maxs];
int inp[32];
int dd[15], cnt[15];

inline int encode(int *p) {
int r = 0;
rep(i, 0, 14) r += p[i] * dd[i];
return r;
}
inline void decode(int x, int *p) {
dwn(i, 14, 0) {p[i] = x / dd[i]; x %= dd[i];}
}
inline void calcu() {
dd[0] = 1;
rep(i, 1, 14) dd[i] = cnt[i - 1] * dd[i - 1];
}
int q[maxs << 1];
int temp;
inline int bfs(int x) {
memset(vis, 0, sizeof (vis));
int tot[15];
int hd, tl;
q[hd = tl = 0] = x;
int s;
int ans = INF;
dist[0] = 0;
while (hd <= tl) {
s = q[hd];
if (s == 0) {ans = min(ans, dist[hd]); ++hd; continue;}
// vis[s] = true;
decode(s, tot);
bool f = false;
int ccnt = 0;
if (tot[13] && tot[14]) {
tot[13] = tot[14] = 0;
f = true;
pu
tot[13] = tot[14] = 1;
}
rep(i, 0, 14) {
if (tot[i]) ++ccnt;
if (tot[i] >= 4) {
tot[i] -= 4;
f = true;
pu
rep(j, 0, 14) if (tot[j]) {
--tot[j];
rep(k, 0, 14) if (tot[k]) {
--tot[k];
f = true;
pu
++tot[k];
}
++tot[j];
}
rep(j, 0, 14) if (tot[j] >= 2) {
tot[j] -= 2;
rep(k, 0, 14) if (tot[k] >= 2) {
tot[k] -= 2;
f = true;
pu
tot[k] += 2;
}
tot[j] += 2;
}
tot[i] += 4;
}//zhadan and sidaier
if (tot[i] >= 2) {
tot[i] -= 2;
f = true;
pu
tot[i] += 2;
}//duizi

if (tot[i] >= 3) {
tot[i] -= 3;
f = true;
pu
rep(j, 0, 14) {
if (i == j) continue;
if (tot[j] >= 1) {
--tot[j];
f = true;
pu
++tot[j];
}//sandaiyi
if (tot[j] >= 2) {
tot[j] -= 2;
f = true;
pu
tot[j] += 2;
}//sandaier
}
tot[i] += 3;
}//sanzhang and sandaiyi, sandaier
}
int lianxu;
rep(i, 0, 7) {
lianxu = 0;
rep(j, i, 11) if (tot[j] >= 1) ++lianxu; else break;
if (lianxu >= 5) {
rep(j, i, i + 3) --tot[j];
rep(j, i + 4, i + lianxu - 1) {
--tot[j];
f = true;
pu
}
rep(j, i, i + lianxu - 1) ++tot[j];
}
}//danshunzi
rep(i, 0, 9) {
lianxu = 0;
rep(j, i, 11) if (tot[j] >= 2) ++lianxu; else break;
if (lianxu >= 3) {
rep(j, i, i + 1) tot[j] -= 2;
rep(j, i + 2, i + lianxu - 1) {
tot[j] -= 2;
f = true;
pu
}
rep(j, i, i + lianxu - 1) tot[j] += 2;
}
}//shuangshunzi
rep(i, 0, 10) {
lianxu = 0;
rep(j, i, 11) if (tot[j] >= 3) ++lianxu; else break;
if (lianxu >= 2) {
tot[i] -= 3;
rep(j, i + 1, i + lianxu - 1) {
tot[j] -= 3;
f = true;
pu
}
rep(j, i, i + lianxu - 1) tot[j] += 3;
}
}//sanshunzi
if (!f) ans = min(ans, dist[hd] + ccnt);
++hd;
}
return ans;
}
int xx, yy;
inline void work() {
memset(cnt, 0, sizeof (cnt));
rep(i, 1, n) {
scanf("%d %d", &xx, &yy);
if (3 <= xx && xx <= 13) inp[i] = xx - 3;
if (xx == 1) inp[i] = 11;
if (xx == 2) inp[i] = 12;
if (xx == 0 && yy == 1) inp[i] = 13;
if (xx == 0 && yy == 2) inp[i] = 14;
++cnt[inp[i]];
}
rep(i, 0, 14) ++cnt[i];
calcu();
rep(i, 0, 14) --cnt[i];
printf("%d\n", bfs(encode(cnt)));
}
int main(int argc, const char *argv[]) {
scanf("%d %d", &T, &n);
while (T--) work();
return 0;
}

0

Yolla LV 8 @ 2015-11-25 17:23:42

#include<cstdio>
#include<algorithm>
#define SC scanf
#define U_(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int s[14],ans;
int t,n;
void dfs(int now){
if(now>=ans)return;
int r=0,a=0,b=0;
U_(i,0,13)if(s[i]==1)a++;
U_(i,0,13)if(s[i]==2)b++;
U_(i,0,13)if(s[i]==4){
r++;
if(a>=2)a-=2;else
if(b>=2)b-=2;else
if(b>=1)b--;
}
U_(i,0,13)if(s[i]==3){
r++;
if(a>=1)a--;else
if(b>=1)b--;
}
ans=min(ans,now+r+a+b);
int j;
U_(i,0,7){
for(j=i;j<12;j++){
s[j]--;
if(s[j]<0)break;
if(j-i>=4)dfs(now+1);
}
if(j==12)j--;
while(j>=i)s[j--]++;
}
U_(i,0,9){
for(j=i;j<12;j++){
s[j]-=2;
if(s[j]<0)break;
if(j-i>=2)dfs(now+1);
}
if(j==12)j--;
while(j>=i)s[j--]+=2;
}
U_(i,0,10){
for(j=i;j<12;j++){
s[j]-=3;
if(s[j]<0)break;
if(j-i>=1)dfs(now+1);
}
if(j==12)j--;
while(j>=i)s[j--]+=3;
}
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);

SC("%d%d",&t,&n);
while(t--){
ans=100000;
int a,b;
U_(i,0,13)s[i]=0;
U_(i,1,n){
SC("%d%d",&a,&b);
if(a==1)s[11]++;else
if(a==2)s[12]++;else
if(a==0)s[13]++;else
s[a-3]++;
}
dfs(0);
printf("%d\n",ans);
}

fclose(stdin);
fclose(stdout);

return 0;
}

题解

24 条题解

斗地主

信息

状态

开发

支持

题解

24 条题解

斗地主

信息

状态

开发

支持

还没有账户？

登录