洛谷 P1855 【榨取kkksc03】题解

思路:DP,01背包

------------
这道题目可以说是一道裸的 01背包,唯一的不同仅仅只是将原来的一维改成了两维。我不明白为什么是一道 普及/提高- 的题,所以在评分时评了普及-。

对于每一个愿望,只有两种选择:要么满足,要么不满足。然后 01背包跑一遍就 AC 了。

$ \rm code $

# include <bits/stdc++.h>
using namespace std;
# define maxM 205
int n, m, t, dp[maxM][maxM]; //定义 dp 数组
int main() {
    cin >> n >> m >> t;
    for(int i = 1, x, y; i <= n; ++i) { //为了方便,省去了两个数组,直接边读边做
        cin >> x >> y;
        for(int j = m; j >= x; --j)
            for(int k = t; k >= y; --k) //注意!里层和中层的两个循环必须是倒序的,否则就变成了完全背包!
                dp[j][k] = max(dp[j][k], dp[j - x][k - y] + 1); //要么不满足,要么满足
    }
    cout << dp[m][t] << endl; //最后输出最大值即可
    return 0;
}

 

上一篇:柯基数据通过Rainbond完成云原生改造,实现离线持续交付客户


下一篇:软件测试环境要不要和软件开发环境隔离?