洛谷P 2668[NOIP 2015 D 1 T 3]闘地主
タイトルの説明
牛は最近闘地主というトランプゲームに夢中になった.闘地主は、黒桃、ハート、梅、角片のAからKに大小王を加えた54枚のカードを使ったトランプゲーム.闘地主では,カードの大きさ関係はカードの数字によって以下のように表される:3<4<5<6<7<8<9<10
今、牛牛はただ知りたいだけで、自分のいくつかのグループの手札に対して、それぞれ少なくとも何回札を出してそれらを打ち切ることができます.彼にこの問題を解決してもらってください.
注意しなければならないのは、本題のゲーム者が毎回手を出すことができるカード型が一般の闘地主と似ていて少し異なることだ.
具体的なルールは次のとおりです.
にゅうしゅつりょくけいしき
入力形式:
1行目には、手札の組数および各手札の枚数を表す2つの正の整数Tnがスペースで区切られている.
次にT組のデータ、各組のデータn行、各行の非負の整数はaibiに1枚のカードを表し、そのうちaiはカードのデジタルを表し、biはカードの花色を表し、中間はスペースで隔てられている.特に、私たちは1でデジタルAを表し、11でデジタルJを表し、12でデジタルQを表し、13でデジタルKを表す.黒桃、紅心、梅、角片はそれぞれ1-4で表される.王さんの表示方法は01で、王さんの表示方法は02です.
出力フォーマット:
全部でT行、1行ごとに1つの整数で、i番目の手札を打つ最小回数を表します.
入出力サンプル
サンプル#1を入力:
出力サンプル#1:
サンプル#2を入力:
出力サンプル#2:
説明
サンプル1説明
全部で1組の手札があって、8枚の札を含みます:角片7、角片8、黒桃9、角片10、黒桃J、黒桃5、角片Aと黒桃A.単順子(角片7、角片8、黒桃9、角片10、黒桃J)、単枚札(黒桃5)および対子札(黒桃Aおよび角片A)を3回で打ち切ることができます.
異なるテストポイントについて、手札グループ数Tと枚数nの規模は以下の通りであることを約束した.
データ保証:すべての手札はランダムに生成されます.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dfs+枝切り
dfsが可能な方法は、最小ステップ数maxを更新し、以降dfsの場合、ステップ数がmaxを超えた場合は直接飛び出します~
結果に影響を与えるのが順子なので、dfsは順子を探せばいいので、答えを更新します.
(それぞれの方法で検索するとTになりますが、私の最初のプログラムのように、涙がいっぱいですね…)
また、カードは1枚、2枚、3枚、4枚とないものがそれぞれ何種類あるかを記入し、それぞれの番号の枚数も単独で記入しますが、色や影響がなく、多くのサイクルを省くことができます.
また、Aと2は後ろに切り替えます!!!
(ルール面では、順子に注意して、二順子と三順子は対数が違います~)
ね、これがTになったプログラム、よくある間違いでしょうね・・・
そしてこれがAです・・・
牛は最近闘地主というトランプゲームに夢中になった.闘地主は、黒桃、ハート、梅、角片のAからKに大小王を加えた54枚のカードを使ったトランプゲーム.闘地主では,カードの大きさ関係はカードの数字によって以下のように表される:3<4<5<6<7<8<9<10
今、牛牛はただ知りたいだけで、自分のいくつかのグループの手札に対して、それぞれ少なくとも何回札を出してそれらを打ち切ることができます.彼にこの問題を解決してもらってください.
注意しなければならないのは、本題のゲーム者が毎回手を出すことができるカード型が一般の闘地主と似ていて少し異なることだ.
具体的なルールは次のとおりです.
にゅうしゅつりょくけいしき
入力形式:
1行目には、手札の組数および各手札の枚数を表す2つの正の整数Tnがスペースで区切られている.
次にT組のデータ、各組のデータn行、各行の非負の整数はaibiに1枚のカードを表し、そのうちaiはカードのデジタルを表し、biはカードの花色を表し、中間はスペースで隔てられている.特に、私たちは1でデジタルAを表し、11でデジタルJを表し、12でデジタルQを表し、13でデジタルKを表す.黒桃、紅心、梅、角片はそれぞれ1-4で表される.王さんの表示方法は01で、王さんの表示方法は02です.
出力フォーマット:
全部でT行、1行ごとに1つの整数で、i番目の手札を打つ最小回数を表します.
入出力サンプル
サンプル#1を入力:
1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1出力サンプル#1:
3
サンプル#2を入力:
1 17
12 3
4 3
2 3
5 4
10 2
3 3
12 2
0 1
1 3
10 1
6 2
12 1
11 3
5 2
12 4
2 2
7 2
出力サンプル#2:
6
説明
サンプル1説明
全部で1組の手札があって、8枚の札を含みます:角片7、角片8、黒桃9、角片10、黒桃J、黒桃5、角片Aと黒桃A.単順子(角片7、角片8、黒桃9、角片10、黒桃J)、単枚札(黒桃5)および対子札(黒桃Aおよび角片A)を3回で打ち切ることができます.
異なるテストポイントについて、手札グループ数Tと枚数nの規模は以下の通りであることを約束した.
データ保証:すべての手札はランダムに生成されます.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dfs+枝切り
dfsが可能な方法は、最小ステップ数maxを更新し、以降dfsの場合、ステップ数がmaxを超えた場合は直接飛び出します~
結果に影響を与えるのが順子なので、dfsは順子を探せばいいので、答えを更新します.
(それぞれの方法で検索するとTになりますが、私の最初のプログラムのように、涙がいっぱいですね…)
また、カードは1枚、2枚、3枚、4枚とないものがそれぞれ何種類あるかを記入し、それぞれの番号の枚数も単独で記入しますが、色や影響がなく、多くのサイクルを省くことができます.
また、Aと2は後ろに切り替えます!!!
(ルール面では、順子に注意して、二順子と三順子は対数が違います~)
ね、これがTになったプログラム、よくある間違いでしょうね・・・
#include //1 ，2 ，3 ，4 ，3+1,3+1*2，4+1+1，5 ， ，
#include
#include
int t,n,x,y,b[14],maxx,k;
void dfs(int u,int v)
{
if(v==maxx) return;
if(u==0 && v=5) //5 , ,
{
for(int j=i;(i-j+1)<=as1;j--) b[i]--;
dfs(u-as1,v+1);for(int j=i;i-j+1<=as1;j--) b[i]++;
}
if(as2>=5)
{
for(int j=i;(i-j+1)<=as2;j--) b[i]-=2;
dfs(u-as2*2,v+1);for(int j=i;i-j+1<=as2;j--) b[i]+=2;
}
if(as3>=5)
{
for(int j=i;(i-j+1)<=as3;j--) b[i]-=3;
dfs(u-as3*3,v+1);for(int j=i;i-j+1<=as3;j--) b[i]+=3;
}
if(b[i]==3) //3+1,3+1*2
{
as3=0;as2++;b[i]=0;dfs(u-2,v+1);b[i]=2; //
for(int j=0;j<=n;j++)
if(b[j] && j!=i)
{
k=b[j];b[j]-=(b[j]>=2 ? 2:1);dfs(u-3-(b[j]>=2 ? 2:1),v+1);b[j]=k;
}
}
if(b[i]==4) //4+1+1
{
for(int ii=0;ii<=n;ii++)
if(b[ii] && ii!=i)
{
for(int j=0;j<=n;j++)
if(b[j] && j!=ii && j!=i)
{
b[ii]--;b[j]--;b[i]=0;
dfs(u-6,v+1);
b[ii]++;b[j]++;b[i]=4;
}
if(b[ii]>=2)
{
b[ii]-=2;b[i]=0;
dfs(u-6,v+1);
b[ii]+=2;b[i]=4;
}
}
b[i]=0;dfs(u-4,v+1);b[i]=4;
}
}
else as1=0;
return;
}
int main()
{
scanf("%d%d",&t,&n);
while(t--)
{
maxx=INT_MAX;
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);b[x]++;
}
dfs(n,0);
printf("%d
",maxx);
}
return 0;
} そしてこれがAです・・・
#include
#include
#include
int t,n,x,y,a[5],b[14],maxx;
int qiu()
{
int tot=0;
memset(a,0,sizeof(a));
for(int i=0;i<=13;i++) a[b[i]]++;
while(a[4] && a[2]>1) a[4]--,a[2]-=2,tot++;
while(a[4] && a[1]>1) a[4]--,a[1]-=2,tot++;
while(a[4] && a[2]) a[4]--,a[2]--,tot++;
while(a[3] && a[2]) a[3]--,a[2]--,tot++;
while(a[3] && a[1]) a[3]--,a[1]--,tot++;
return tot+a[1]+a[2]+a[3]+a[4];
}
void dfs(int u) // , ,
{
if(u>=maxx) return;int kk=qiu();
if(u+kk=3 && j<=13) j++;
if(j-i>=2)
for(int v=i+1;v<=j-1;v++)
{
for(int vk=i;vk<=v;vk++) b[vk]-=3;
dfs(u+1);
for(int vk=i;vk<=v;vk++) b[vk]+=3;
}
}
for(int i=2;i<=13;i++)
{
int j=i;
while(b[j]>=2 && j<=13) j++;
if(j-i>=3)
for(int v=i+2;v<=j-1;v++)
{
for(int vk=i;vk<=v;vk++) b[vk]-=2;
dfs(u+1);
for(int vk=i;vk<=v;vk++) b[vk]+=2;
}
}
for(int i=2;i<=13;i++)
{
int j=i;
while(b[j]>=1 && j<=13) j++;
if(j-i>=5)
for(int v=i+4;v<=j-1;v++)
{
for(int vk=i;vk<=v;vk++) b[vk]--;
dfs(u+1);
for(int vk=i;vk<=v;vk++) b[vk]++;
}
}
}
int main()
{
scanf("%d%d",&t,&n);
while(t--)
{
maxx=INT_MAX;
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
if(x==1) x=13;
else if(x) x--;
b[x]++;
}
dfs(0);
printf("%d
",maxx);
}
return 0;
}