POJ 2392 Space Elevator

問題文

DP強化週間。

K種類のブロックがある。種類iのブロックは高さhi、個数ci個ある。
そして様々なブロックを下から積み上げて行った時、この種類のブロックは
必ずai以下に置かれていなくてはならない。積み上げることのできるブロックの
最長の長さを答える。という問題。

同じ種類のブロックをまとめておけばいいので、ブロックの限界高さでソートして
あとは配るDP（って言うのかな?）すればいい。
dp[i]:=(高さiに積み上げられるか)でbool DP。どのブロックも40000以下の高さにしか置けないので40000以下で置けるところをブロックの種類を変えて毎回探せばいい。ただansより上は常にfalseになっているので40000をansに変えたほうが賢い。中国の人のブログだとそうしていた。
でも40000でも何とか通る。

以下ソース。

struct block{
  int h, a, c;
  bool operator<(const block &r)const{
    return a < r.a;
  }
};

block b[410];
bool dp[50000];

int main(){
  int K; cin >> K;
  for(int i = 0; i < K; i++) {
    cin >> b[i].h >> b[i].a >> b[i].c;
  }

  sort(b, b + K);
  int ans = 0;
  dp[0] = true;
  for(int i = 0; i < K; i++){
    for(int j = 40000; j >= 0; j--){
      if(dp[j]){
	for(int k = 1; k <= b[i].c; k++){
	  if(j + k * b[i].h > b[i].a) break;
	  dp[j + k * b[i].h] = true;
	  ans = max(ans, j + k * b[i].h);
	}
      }
    }
  }
  cout << ans << endl;
  return 0;
}

貪欲でもいけそうな気もするが。