Codeforces ECR #058 : F. Trucks and Cities

これ系のDP苦手なので、解けて良かった。
https://codeforces.com/contest/1101/problem/F

問題

N個の町が１列に並んでおり、それぞれの位置が与えられる。
ここで以下M台のトラックの情報が与えられる。

トラックiはS[i]番からT[i]番の町へ移動する。
燃費は1kmあたりC[i]リットルである。
トラックはガソリン満タンで走りはじめ、移動の途中町を通る際、最大K回までガソリンを満タンに補給できる。

全トラックが走りきれる最小のガソリンタンクの容量を答えよ。

解法

以下を求めてしまおう。
dp(L,R,n) := 町LからRに移動する際、n回までガソリンを補給できるとき、補給せずに走らないといけない最大区間長
そうすると、解は各クエリにおけるdp(S[i],T[i],K[i])*C[i]の最大値を答えればよくなる。

dp(L,R,n)がすでに求まっているとき、n回目の補給位置をXとする。
その場合、dp(L,R+1,n)を求めたい場合、補給位置はX以降になる。
これにより、均しでdp(L,*,n)はO(N)で求めることができ、テーブル全体はO(N^3)で求められる。

int N,M;
int A[404];

int dp[404][404][404];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	for(i=1;i<=N;i++) cin>>A[i];
	
	FOR(i,404) FOR(x,404) FOR(y,404) dp[i][x][y]=1<<30;
	FOR(y,404) FOR(x,y+1) dp[x][y][0]=A[y]-A[x];
	for(i=1;i<=400;i++) {
		for(x=1;x<=N;x++) {
			r=x;
			for(y=x+i+1;y<=N;y++) {
				while(max(dp[x][r][i-1],dp[r][y][0])>=max(dp[x][r+1][i-1],dp[r+1][y][0])) r++;
				dp[x][y][i]=max(dp[x][r][i-1],dp[r][y][0]);
			}
		}
	}
	
	ll ma=0;
	FOR(i,M) {
		cin>>x>>y>>j>>k;
		k=min(k,y-x-1);
		x=dp[x][y][k];
		ma=max(ma,1LL*x*j);
	}
	cout<<ma<<endl;
	
}

まとめ

Monge性とか良くわかってないけど関係ある？