|
题目描述
洛谷的运营组决定，如果一名 OIer 向他的教练推荐洛谷，并能够成功的使用（成功使用的定义是：该团队有 2020 个或以上的成员，上传 1010 道以上的私有题目，布置过一次作业并成功举办过一次公开比赛），那么他可以浪费掉 kkksc03 的一些时间的同时消耗掉 kkksc03 的一些金钱以满足自己的一个愿望。
kkksc03 的时间和金钱是有限的，所以他很难满足所有同学的愿望。所以他想知道在自己的能力范围内，最多可以完成多少同学的愿望？
输入格式
第一行三个整数 n,M,Tn,M,T，表示一共有 nn（1 \le n \le 1001≤n≤100）个愿望， kkksc03 的手上还剩 MM（0 \le M \le 2000≤M≤200）元，他的暑假有 TT（0 \le T \le 2000≤T≤200）分钟时间。
第 22~n+1n+1 行
表示第 i个愿望所需要的金钱和时间。
输出格式
一行，一个数，表示 kkksc03 最多可以实现愿望的个数。
输入输出样例
输入 #1复制
6 10 10
1 1
2 3
3 2
2 5
5 2
4 3
输出 #1复制
4
解题思路
这也是很经典的一个双限制背包问题，之前发过一道单限制的背包问题，这个解题思路呢和之前的单限制背包问题解题思路是一样的，那就是dp的核心了，怎么才能推出dp的动态转移方程呢？
和之前的一样：首先我们看有几个限制条件，两个，所以我们定义一个三维数组：f[n][T][M] n:第几个愿望，T和M遍历到这个愿望时花费T时间M的金钱， f[n][T][M]存的数就是当前我花时间T金钱M可以实现的愿望，好了这就简单了。
所以状态转移方程我们就能推出来：
if (j >= yw[i].second && k >= yw[i].first) {//j:所花时间,k:所化金钱
int ywnum = f[i - 1][j - yw[i].second][k - yw[i].first];
f[i][j][k] = max(f[i - 1][j][k], ywnum + 1);
}
else
f[i][j][k] = f[i - 1][j][k];
所以最终的总代码：
AC代码
#include <iostream>
#include<map>
using namespace std;
pair<int, int>yw[105];//first：金钱,second:时间
int n, T, M, f[105][205][205];//n个愿望，M金钱，T时间
int main() {
int Mx = 0;
cin >> n >> T >> M;
for (int i = 1; i <= n; i++) {
cin >> yw[i].first >> yw[i].second;
}
for (int i = 1; i <= n; i++) {//愿望个数
for (int j = 1; j <= T; j++) {//这个愿望的时间
for (int k = 1; k <= M; k++) {//这个愿望的金钱
if (j >= yw[i].second && k >= yw[i].first) {
int ywnum = f[i - 1][j - yw[i].second][k - yw[i].first];
f[i][j][k] = max(f[i - 1][j][k], ywnum + 1);
}
else
f[i][j][k] = f[i - 1][j][k];
}
}
}
cout << f[n][T][M];
return 0;
}
|