洛谷p1509 找啊找啊找GF

本文主要是介绍洛谷p1509 找啊找啊找GF，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一道二维费用背包变形
题目链接

思路

两个限制条件都要满足：人品，人民币，所以用二维费用背包
要求，泡最多的mm，和花费时间最少，所以需要有一个背包是时间，而很明显本题中物品是每个mm，所以用另一个背包存人数，判断是否需要转移

ACcode

#include<bits/stdc++.h>using namespace std;const int M = 1e4 + 9;
using ll = long long;
ll dp1[M][M], dp2[M][M], t[M], rp[M], v[M];int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n;cin >> n;for (int i = 1;i <= n;i++)cin >> v[i] >> rp[i] >> t[i];ll m, r;cin >> m >> r;for (int i = 1;i <= n;i++) {for (int j = m;j >= v[i];j--) {for (int h = r;h >= rp[i];h--) {if (dp1[j][h] < dp1[j - v[i]][h - rp[i]] + 1) {dp1[j][h] = dp1[j - v[i]][h - rp[i]] + 1;dp2[j][h] = dp2[j - v[i]][h - rp[i]] + t[i];}else if (dp1[j][h] == dp1[j - v[i]][h - rp[i]]+1) {dp2[j][h] = min(dp2[j][h], dp2[j - v[i]][h - rp[i]]+t[i]);}}}}cout << dp2[m][r];return 0;
}

这篇关于洛谷p1509 找啊找啊找GF的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---