c++P1156 垃圾陷阱

题目描述：卡门掉进了一个井里，井的深度为d，卡门的身高为h，卡门想要爬出井外，井外有一堆垃圾，卡门可以通过吃垃圾来维持生命，每吃一堆垃圾可以增加卡门的身高1，卡门可以把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。现在给出卡门吃每堆垃圾的时间和每堆垃圾的高度，请你编写一个程序，计算卡门最少需要吃多少堆垃圾才能够爬出井外。

思路：动态规划。设dp[i][j]表示吃了前i堆垃圾，身高为j时的最小时间。则状态转移方程为：dp[i][j] = min(dp[i-1][j]+1, dp[i-1][j-h[i]]+1)，其中h[i]表示第i堆垃圾的高度。最终答案为min{dp[n][j]}，其中n为垃圾的堆数，j为满足条件的最小身高。

以下是C++代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110, M = 1010;
int dp[N][M], h[N], t[N];

int main()
{
    int d, n;
    cin >> d >> n;
    for (int i = 1; i <= n; i ++ ) cin >> t[i] >> h[i];

    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= d; j ++ )
            if (j + h[i] >= d)
                dp[i][d] = min(dp[i][d], dp[i-1][j] + t[i]);
            else
                dp[i][j+h[i]] = min(dp[i][j+h[i]], dp[i-1][j] + t[i]);

    int res = 0x3f3f3f3f;
    for (int i = 0; i <= d; i ++ ) res = min(res, dp[n][i]);
    cout << res << endl;

    return 0;
}