PKU 2353 Ministry
http://poj.org/problem?id=2353
各階にn個部屋があるm階建ての建物がある。
F氏は代表者の認可が欲しいが、この建物の人はその人がいる隣の部屋か、下の階の同じ番号の部屋にいる人の認可がなければ認可してくれない。
1階にいる人は無条件で認可してくれる。
このとき、各部屋で認可をもらうためのコストがわかっている時、最小のコストでM階の人の認可をもらえるような巡回経路を答えろというような問題。
DP+経路復元。
DP部分をメモ化再帰でやろうとして上手く書けずに諦めました。
ll dp[100][500]; ll in[100][500]; void print_path(int fl,int ro){ if(fl){ if(dp[fl-1][ro]+in[fl][ro]==dp[fl][ro]) print_path(fl-1,ro); else if(ro && dp[fl][ro-1]+in[fl][ro]==dp[fl][ro]) print_path(fl,ro-1); else print_path(fl,ro+1); } cout<<ro+1<<endl; } main(){ int m,n; cin>>m>>n; rep(i,m)rep(j,n)scanf("%lld",in[i]+j); rep(i,n)dp[0][i]=in[0][i]; for(int i=1;i<m;++i){ for(int j=0;j<n;++j) dp[i][j]=in[i][j]+dp[i-1][j]; for(int j=1;j<n;++j) dp[i][j]=min(dp[i][j],dp[i][j-1]+in[i][j]); for(int j=n-2;j>=0;--j) dp[i][j]=min(dp[i][j],dp[i][j+1]+in[i][j]); } ll ans=*min_element(dp[m-1],dp[m-1]+n); rep(i,n){ if(ans!=dp[m-1][i])continue; print_path(m-1,i); break; } }