PKU 3230 Travel
http://poj.org/problem?id=3230
ある旅行者がn個の街をm日間かけて旅行する。このとき、都市iから都市jにいどうするにはコストがかかるが、k日に都市lでは一定の収入が得られる。
旅行者は必ず1からスタートするとき、m日後に最大の所持金はいくらかという問題。
BFSだとTLEしそうだったので、動的計画法に持ち込みました。
dp[都市番号][何日後]=最大の所持金、みたいな感じです。
int cost[100][100]; int income[100][100]; int dp[100][2]; main(){ int n,m; while(cin>>n>>m,n|m){ rep(i,n)rep(j,n)cin>>cost[i][j]; rep(i,m)rep(j,n)cin>>income[i][j]; rep(i,n)dp[i][0]=dp[i][1]=INT_MIN/3; dp[0][0]=0; int ans=INT_MIN/3; rep(i,m){ rep(j,n){ rep(k,n){ dp[j][i+1&1]=max(dp[j][i+1&1],dp[k][i&1]-cost[k][j]+income[i][j]); } } } rep(i,n)ans=max(ans,dp[i][m&1]); cout<<ans<<endl; } }