题目地址:http://poj.org/problem?id=2392

题目大意

大致意思是,有$K$种石头,每种石头有高度$h$,最大高度$a$(当前石头的总高度不能超过该石头的最大高度),数量$c$,求问能堆成最大高度是多少?

思路

多重背包系列,首先按照$a$从小到大排序,设$visited[h]$为标记能否堆成$h$高度,$sum[h]$表示该石块堆成$h$所需要的数量。

AC代码

/*************************************************************************
    > File Name: 2392.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-10-15 四 16:09:51 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int K;
struct block {
    int h, a, c; // 高度,海拔,个数
    bool operator<(const block &b) const {
        return a < b.a;
    }
} blocks[402];

bool visited[40025]; // visited[i]标记能堆成高度i
int sum[40025];


void solve() {
    sort(blocks, blocks+K); // 按照a由小大到排序
    memset(visited, 0, sizeof(visited));
    visited[0] = true; // 初始化,高度0能堆成
    int ans = 0; // 最大高度
    for(int i=0; i<K; ++i) {
        memset(sum, 0, sizeof(sum));
        for(int j=blocks[i].h; j<=blocks[i].a; ++j) {
            if(!visited[j] && visited[j-blocks[i].h] && sum[j-blocks[i].h] < blocks[i].c) { // 若当前高度$j$不能堆成,但$j-blocks[i].h$高度能堆成,并且数量够,则利用这块堆成$j$
                visited[j] = true;
                sum[j] = sum[j-blocks[i].h] + 1;
                ans = max(j, ans);
            }
        }
    }
    cout << ans << endl;
}

int main()
{
#ifdef Oj
    freopen("2392.in", "r", stdin);
#endif
    cin >> K;
    for(int i=0; i<K; ++i) {
        cin >> blocks[i].h >> blocks[i].a >> blocks[i].c;
    }
    solve();
    return 0;
}