これはすんなり。
https://yukicoder.me/problems/no/2916
問題
N点M辺の有向グラフがある。
各辺vにはR[v]、W[v]が指定されており、現所持金cに対し、floor(c/R[v])+W[v]支払って辺に沿って移動ができる。(所持金がマイナスになる移動は不可)
C=1~cのそれぞれに対し、初期状態で所持金Cで頂点1にいる人が、頂点Nに移動できるか。
また可能なら残金に最大値を求めよ。
解法
dp(v,c) := 頂点vに残金cの状態でいる場合、頂点Nに最大どれだけ残金を残して移動できるか
このテーブルを埋めて行けばよい。
dp(N,c) = cから初めてcの小さい順にテーブルを埋め、dp(1,c)の値を答えればよい。
int N,M,C; ll dp[10][101010]; vector<vector<int>> E[10]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>C; FOR(i,M) { cin>>x>>y>>k>>r; E[x-1].push_back({y-1,k,r}); E[y-1].push_back({x-1,k,r}); } FOR(i,C+1) { FOR(j,N) dp[j][i]=-1; dp[N-1][i]=i; FOR(j,N) FORR(e,E[j]) { int c=i/e[1]+e[2]; if(c<=i) dp[j][i]=max(dp[j][i],dp[e[0]][i-c]); } } for(i=1;i<=C;i++) cout<<dp[0][i]<<endl; }
まとめ
これすんなり思い浮かんだけど、Editorialでは4番目に来る解法なんだな。