PKU 2111 Millenium Leapcow
http://poj.org/problem?id=2111
n*nのボードに1〜n*nまでの番号が適当に振られている。
この時、あるマスからスタートしてチェスのナイトの動きで現在いるマスより高い数値のマスに移動することができる。
最長手数かつ、辞書順最小な経路を出力しろというような問題。
メモ化再帰+経路復元しました。
cinでTLEもらいました。
int dx[]={1,2,2,1,-1,-2,-2,-1},dy[]={2,1,-1,-2,-2,-1,1,2}; int memo[400][400]; int in[400][400]; int n; int rec(int x,int y){ if(memo[x][y])return memo[x][y]; int & ret=memo[x][y]=1; rep(i,8){ int nx=x+dx[i],ny=y+dy[i]; if(0>nx || nx>=n || 0>ny || ny>=n || in[nx][ny]<in[x][y])continue; ret=max(ret,rec(nx,ny)+1); } return ret; } void print_path(int x,int y){ int idx=8; int za=n*n+2; int nx,ny; rep(i,8){ int tnx=x+dx[i],tny=y+dy[i]; if(0>tnx || tnx>=n || 0>tny || tny>=n || in[x][y]>in[tnx][tny])continue; if(memo[tnx][tny]+1==memo[x][y] && za>in[tnx][tny]){ za=in[tnx][tny]; idx=i; nx=tnx; ny=tny; } } cout<<in[x][y]<<endl; if(idx!=8)print_path(nx,ny); } main(){ cin>>n; rep(i,n)rep(j,n)scanf("%d",in[i]+j); pair<PI,PI> ans(mp(0,0),mp(0,0)); rep(i,n)rep(j,n) ans=max(ans,mp(mp(rec(i,j),-in[i][j]),mp(i,j))); cout<<ans.F.F<<endl; print_path(ans.S.F,ans.S.S); }