蟻本の練習問題を消化中
概要
K種類のブロックがあって,i番目のブロックは高さhiであり,ci個だけある.また,ブロックの一部がhiを超えるとまずい.
ブロックを積み上げていくとき,到達できる高さの最大はいくつか.
解法
ブロックを高さ制限でソート.
dp[i][j]:=(高さjへ到達するために必要なブロックの最少数.不可能なら-1)
としてDPを行う.
struct Block{ int h, a, c; Block(int h, int a, int c) : h(h),a(a),c(c) {} Block() {} }; bool operator<(const Block &a, const Block &b){ return a.a < b.a; } int K; int dp[40010]; Block b[400]; int main(){ scanf("%d", &K); for(int i = 0; i < K; ++i){ int h, a, c; scanf("%d%d%d", &h, &a, &c); b[i] = Block(h, a, c); } sort(b, b + K); memset(dp, -1, sizeof(dp)); dp[0] = 0; for(int i = 0; i < K; ++i){ for(int j = 0; j <= b[i].a; ++j){ if(dp[j] >= 0) dp[j] = b[i].c; if(j >= b[i].h) dp[j] = max(dp[j], dp[j-b[i].h] - 1); } } int r; for(r = 40000; ; --r) if(dp[r] >= 0) break; printf("%d\n", r); return 0; }