P1242 新汉诺塔
此题的最后一个数据点不适用于贪心算法,所以每次将大的优先移到目标位置有很小的概率不是最优解,但是毕竟是最优解的概率还是很大的。所以用模(yi)拟(tong)退(luan)火(gao)就可以了,反正也是随机碰碰运气的。概率嘛~~~~,只要你的srand能过,那就能过啦。
//退火算法,洛谷hack掉了贪心,无语了。 #include<cstdio> #include<cstdlib> #include<iostream> using namespace std; #define MAXN 100 #define MAXM 1000000 #define INF 2000000000 int n,m,x,ans=INF,tans,cnt; int A[MAXN],B[MAXN],tA[MAXN],tB[MAXN]; int tI[MAXM],tX[MAXM],tY[MAXM],I[MAXM],X[MAXM],Y[MAXM]; char p[5]={'\0','A','B','C'}; void dfs(int id,int b) { if(tA[id]==b)return ; for(int i=id-1;i>=1;i--) dfs(i,6-tA[id]-b); cnt++; tI[cnt]=id; tX[cnt]=tA[id]; tY[cnt]=b; //printf("move %d from %c to %c\n",id,p[tA[id]],p[b]); tans++; tA[id]=b; } void update() { ans=tans; for(int i=1;i<=cnt;i++) { I[i]=tI[i]; X[i]=tX[i]; Y[i]=tY[i]; } } void print() { for(int i=1;i<=ans;i++) printf("move %d from %c to %c\n",I[i],p[X[i]],p[Y[i]]); printf("%d\n",ans); } int main() { scanf("%d",&n); for(int i=1;i<=3;i++) { scanf("%d",&m); for(int j=1;j<=m;j++) { scanf("%d",&x); A[x]=i; } } for(int i=1;i<=3;i++) { scanf("%d",&m); for(int j=1;j<=m;j++) { scanf("%d",&x); B[x]=i; } } srand(19260817); for(int G=1;G<=100;G++) { tans=0; cnt=0; for(int i=1;i<=n;i++) tA[i]=A[i], tB[i]=B[i]; for(int i=n;i>=1;i--) if(rand()%(n-i+2)==0) dfs(i,6-A[i]-B[i]);//这里必须写(n-i+2),这是退火的精髓?其实我可能要再去看一看。呵呵。 else dfs(i,B[i]); for(int i=n;i>=1;i--) dfs(i,B[i]); if(tans<ans) update(); } print(); return 0; }