AtCoder Regular Contest #073
AtCoder Beginner Contest #060
問題文 (ARC)
問題文 (ABC)
$N$ 種のアイテムが $1$ 個ずつあって,$i$ 番目のアイテムの価値は $V_i$,重さは $H_i$ である.
バッグには合計で重さ $W$ まで入れることができる.
バッグに入れるアイテムの価値の合計値を最大化した時,その最大値を求める問題.
重さの種類数が $4$ 種類しかないので,アイテムを重さに応じて $4$ 種類に分類する.
後は,同じ重さなら価値が高い方からバッグに詰めれば良いので,各価値のアイテムを何個積めるかを全探索する.
$3$ 種類について,何個入れるかを決めると,最後の種類について何個入れるかは(できるだけ入れたほうが良いので)一意に定まる.
よって,時間計算量は $O(N^3)$ 程度でできる.
C++に変換後のコードはこちら
int N, W, H[100], V[100];
int gain[4][100], sum[4][101], sz[4];
{
int res = 0;
int a, b, c, d;
ll r, minH;
rd(N, W, (H,V)(N));
minH = H[0];
H[0..N-1] -= minH;
gain[H[0..N-1]][sz[H[0..]]++] = V[0..];
sort(gain[0..3], gain[0..]+sz[0..], greater<int>());
sum[0...3][1..sz[0...]] += sum[0...][0..] + gain[0...][0..];
rep(a,sz[0]+1) rep(b,sz[1]+1) rep(c,sz[2]+1){
r = W - minH*a - (minH+1)*b - (minH+2)*c;
if(r < 0) break;
d = min(r / (minH+3), (ll)sz[3]);
res >?= sum[0][a] + sum[1][b] + sum[2][c] + sum[3][d];
}
wt(res);
}
Current time: 2024年03月28日19時14分35秒
Last modified: 2017年04月29日23時01分12秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest AtCoder_Beginner_Contest ARC073 ARC_B ABC060 ABC_D
トップページに戻る
Logged in as: unknown user (not login)