kmjp's blog

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

Indeedなう(本選A) : C - Optimal Recommendations

気づいてしまえばあっさり。
http://indeednow-finala-open.contest.atcoder.jp/tasks/indeednow_2015_finala_c

問題

N個の職種があり、その給与はW[i]である。
各職種に就くには3種のパラメータがそれぞれA[i],B[i],C[i]以上でなければならない。

ここでM人の人がおり、その3種のパラメータはX[i],Y[i],Z[i]である。
各人が就ける職業における最高額の給与を求めよ。

解法

パラメータの上限は高々100であり、パラメータの組み合わせは101*101*101である。
よってDPで全パラメータの組み合わせにおける最高額を求めてしまえば、あとはクエリは簡単に処理できる。

3つのパラメータが(a,b,c)の人が得られる最高給与をE(a,b,c)とする。
E(a,b,c)=max(E(a-1,b,c),E(a,b-1,c),E(a,b,c,-1),ちょうどそのパラメータで就ける職種iのW[i])という割と単純なDPでEを求められる。

int N,M;
int dp[105][105][105];

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N>>M;
	while(N--) cin>>x>>y>>z>>r, dp[x][y][z]=max(dp[x][y][z],r);
	FOR(x,101) FOR(y,101) FOR(z,101) {
		dp[x+1][y][z]=max(dp[x+1][y][z],dp[x][y][z]);
		dp[x][y+1][z]=max(dp[x][y+1][z],dp[x][y][z]);
		dp[x][y][z+1]=max(dp[x][y][z+1],dp[x][y][z]);
	}
	while(M--) cin>>x>>y>>z, cout<<dp[x][y][z]<<endl;
}

まとめ

幸いこれはすんなり思いついた。