解析

應(yīng)該從大到小一個(gè)個(gè)移，這樣后面大盤就可以直接忽略，保證沒有冗余操作，必定最優(yōu)（如果先移動(dòng)小的，后面移動(dòng)大的時(shí)還要?jiǎng)有〉?#xff09;
對(duì)于第id個(gè)從當(dāng)前位置到目標(biāo)的移動(dòng)有兩種移動(dòng)方案：
法1：把id-1個(gè)移到中轉(zhuǎn)站，把id移到目標(biāo)
法2：把id-1個(gè)移到id的目標(biāo)，把id移到中轉(zhuǎn)站，把id-1個(gè)都移到id原位置，把id移到目標(biāo)
洛谷很多題解都只考慮了第一種方案，但在加入數(shù)據(jù)11后會(huì)被卡掉
法2雖然看起來繁瑣，但其好處是第id-1個(gè)會(huì)落到id的原位置，當(dāng)其目標(biāo)恰好是這個(gè)位置，且其原位置在id的目標(biāo)（這樣法2的第一步就不用處理id-1）時(shí)，我們只需要處理一次id-1的移動(dòng)，而用法1需處理2次，故此時(shí)法2更優(yōu)

代碼

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int place[50020],now,goal,ans[50020]; int n; char s[10]={'m','A','B','C','f','u','c','k'}; long long tot=0; void move(int id,int to){if(place[id]==to) return;int spj=0;int trans=6-place[id]-to;if(place[id-1]!=to) spj=1;//只有當(dāng)下一個(gè)盤（id-1）目前在id的目標(biāo)且其目標(biāo)在id目前的位置時(shí)觸發(fā)特判 if(ans[id-1]!=place[id]) spj=1;//if(id==1) spj=1; 這行似乎不加也行 if(spj==0){//spj：方法2 for(int i=id-1;i>=1;i--) move(i,to);printf("move %d from %c to %c\n",id,s[place[id]],s[trans]);tot++;place[id]=trans;for(int i=id-1;i>=1;i--) move(i,6-place[id]-to);printf("move %d from %c to %c\n",id,s[place[id]],s[to]);tot++;place[id]=to;return;}//正常：方法1 for(int i=id-1;i>=1;i--) move(i,6-place[id]-to);printf("move %d from %c to %c\n",id,s[place[id]],s[to]);place[id]=to;++tot; } int main(){int num;scanf("%d",&n);for(int i=1;i<=3;i++){scanf("%d",&num);for(int j=1;j<=num;j++){scanf("%d",&now);place[now]=i;}}for(int i=1;i<=3;i++){scanf("%d",&num);for(int j=1;j<=num;j++){scanf("%d",&goal);ans[goal]=i;}}//if(n==3&&place[1]==3&&ans[1]==1){//printf("move 3 from A to B\n");//place[3]=2;//tot++;//}for(int i=n;i>=1;i--){if(place[i]==ans[i]) continue;move(i,ans[i]);}printf("%lld",tot);return 0; }

反數(shù)據(jù)大全

自己調(diào)時(shí)洛谷基本都能過（too water。。）
但自己又想到一些反數(shù)據(jù)卡掉了一些不成熟的想法（基于數(shù)據(jù)11）
如果洛谷和這些數(shù)據(jù)你都能過，那么基本沒問題啦~~
（限于篇幅輸出只顯示步數(shù)）
case 1
in：
3
1 3
0
2 2 1
2 2 1
0
1 3

out：
5

case 2
in：
4
1 3
1 4
2 2 1
2 2 1
1 4
1 3

out：
5

case 3
in：
3
1 3
0
2 2 1
1 2
1 1
1 3

out：
6

case 4
in：
4
2 4 1
0
2 3 2
3 3 2 1
0
1 4

out：
10

Ending

你又變厲害了呢~~~
祝大家AKNOI，rp++！！

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的新汉诺塔（洛谷P1242）含第11个数据的解决办法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。