kmjp's blog

競技プログラミング参加記です

yukicoder : No.2916 累進コスト最小化

これはすんなり。
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番目に来る解法なんだな。