Luogu P1509 找啊找啊找GF

• 题目背景
• 题目描述
• 输入格式
• 输出格式
• 输入输出样例
• 输入 #1 复制
• 输出 #1 复制
• 说明/提示
• 数据规模
• 解析
• 代码

题目背景

“找啊找啊找GF,找到一个好GF,吃顿饭啊拉拉手,你是我的好GF.再见.”
“诶,别再见啊…”
七夕…七夕…七夕这个日子,对于$sqybi$sqybi这种单身的菜鸟来说是多么的痛苦…虽然他听着这首叫做"找啊找啊找GF"的歌,他还是很痛苦.为了避免这种痛苦,$sqybi$sqybi决定要给自己找点事情干.他去找到了七夕模拟赛的负责人$zmc MM$zmcMM,让她给自己一个出题的任务.经过几天的死缠烂打,$zmc MM$zmcMM终于同意了.
但是,拿到这个任务的$sqybi$sqybi发现,原来出题比单身更让人感到无聊 $-\_-...$−_−... 所以,他决定了,要在出题的同时去办另一件能够使自己不无聊的事情–给自己找GF.
$sqybi$sqybi现在看中了$n$n个$MM$MM,我们不妨把她们编号$1$1到$n$n.请$MM$MM吃饭是要花钱的,我们假设请$i$i号MM吃饭要花$rmb[i]$rmb[i]块大洋.而希望骗$MM$MM当自己$GF$GF是要费人品的,我们假设请第$i$i号$MM$MM吃饭试图让她当自己$GF$GF的行为(不妨称作泡该$MM$MM)要耗费$rp[i]$rp[i]的人品.而对于每一个$MM$MM来说,$sqybi$sqybi都有一个对应的搞定她的时间,对于第$i$i个$MM$MM来说叫做$time[i]$time[i]. $sqybi$sqybi保证自己有足够的魅力用$time[i]$time[i]的时间搞定第$i$i个$MM$MM^_^.
$sqybi$sqybi希望搞到尽量多的$MM$MM当自己的$GF$GF,这点是毋庸置疑的.但他不希望为此花费太多的时间(毕竟七夕赛的题目还没出),所以他希望在保证搞到$MM$MM数量最多的情况下花费的总时间最少.

题目描述

$sqybi$sqybi现在有$m$m块大洋,他也通过一段时间的努力攒到了$r$r的人品(这次为模拟赛出题也攒$rp$rp哦~~).他凭借这些大洋和人品可以泡到一些$MM$MM.他想知道,自己泡到最多的$MM$MM花费的最少时间是多少.
注意$sqybi$sqybi在一个时刻只能去泡一个$MM$MM–如果同时泡两个或以上的$MM$MM的话,她们会打起来的…

输入格式

输入的第一行是$n$n,表示$sqybi$sqybi看中的$MM$MM数量.
接下来有$n$n行,依次表示编号为$1, 2, 3, ..., n$1,2,3,...,n的一个$MM$MM的信息.每行表示一个$MM$MM的信息,有三个整数:$rmb, rp$rmb,rp和$time$time.
最后一行有两个整数,分别为$m$m和$r$r.

输出格式

你只需要输出一行,其中有一个整数,表示$sqybi$sqybi在保证$MM$MM数量的情况下花费的最少总时间是多少.

输入输出样例

输入 #1 复制

4
1 2 5
2 1 6
2 2 2
2 2 3
5 5

输出 #1 复制

13

说明/提示

$sqybi$sqybi说:如果题目里说的都是真的就好了…
$sqybi$sqybi还说,如果他没有能力泡到任何一个$MM$MM,那么他就不消耗时间了(也就是消耗的时间为$0$0),他要用这些时间出七夕比赛的题来攒$rp$rp…

数据规模

对于$20\%$20%数据,$1\le n\le 10$1≤n≤10;
对于$100\%$100%数据,$1\le rmb\le100,1\le rp\le100,1\le time\le1000$1≤rmb≤100,1≤rp≤100,1≤time≤1000;
对于$100\%$100%数据,$1\le m\le100,1\le r\le100,1\le n\le100$1≤m≤100,1≤r≤100,1≤n≤100

解析

一个没有那么简单的二维背包题。
题目中给出的限制条件是在能泡到的MM最多的情况下耗费的时间最少，so我们就用两个dp数组，分别存能泡到MM的数量和耗费的时间。
根据01背包的状态转移方程容易得知，此题的状态转移方程为：当
$dpnum[j][k]&lt;=dpnum[j-rmb[i]][k-rp[i]]+1$dpnum[j][k]<=dpnum[j−rmb[i]][k−rp[i]]+1时，$dpnum[j][k]=dpnum[j-rmb[i]][k=rp[i]]+1$dpnum[j][k]=dpnum[j−rmb[i]][k=rp[i]]+1,
$dptime[j][k]=min(dptime[j][k],dptime[j-rmb[i]][k-rp[i]]+time[i])$dptime[j][k]=min(dptime[j][k],dptime[j−rmb[i]][k−rp[i]]+time[i])。
$(1&lt;=i&lt;=n, rmb[i]&lt;=j&lt;=m, rp[i]&lt;=k&lt;=r)$(1<=i<=n,rmb[i]<=j<=m,rp[i]<=k<=r)

代码

#include<iostream>
#define inf 0x7fffffff
using namespace std;
struct node {
	int num, time;
} dp[1001][1001];					//把两个dp放在一起了
int rmb[101];
int rp[101];
int t[101];
int main() {
	int r, m, n;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> rmb[i] >> rp[i] >> t[i];
	}
	cin >> m >> r;
	for(int i = 1; i <= n; i++) {
		for(int j = m; j >= rmb[i]; j--) {
			for(int k = r; k >= rp[i]; k--) {
				if(dp[j][k].num < dp[j - rmb[i]][k - rp[i]].num + 1) {
					dp[j][k].num = dp[j - rmb[i]][k - rp[i]].num + 1;
					dp[j][k].time = dp[j - rmb[i]][k - rp[i]].time + t[i];
				} else if(dp[j][k].num == dp[j - rmb[i]][k - rp[i]].num + 1) {
					dp[j][k].time = min(dp[j][k].time, dp[j - rmb[i]][k - rp[i]].time + t[i]);
				}
			}
		}
	}
	cout << dp[m][r].time;
	return 0;
}