找啊找啊找GF

题目背景

“找啊找啊找 GF，找到一个好 GF，吃顿饭啊拉拉手，你是我的好 GF。再见。”

“诶，别再见啊…”

七夕… 七夕… 七夕这个日子，对于 sqybi 这种单身的菜鸟来说是多么的痛苦… 虽然他听着这首叫做“找啊找啊找 GF”的歌，他还是很痛苦。为了避免这种痛苦，sqybi 决定要给自己找点事情干。他去找到了七夕模拟赛的负责人 zmc MM，让她给自己一个出题的任务。经过几天的死缠烂打，zmc MM 终于同意了。

但是，拿到这个任务的 sqybi 发现，原来出题比单身更让人感到无聊 -_- … 所以，他决定了，要在出题的同时去办另一件能够使自己不无聊的事情——给自己找 GF。

题目描述

sqybi 现在看中了 $n$ 个 MM，我们不妨把她们编号 $1$ 到 $n$。请 MM 吃饭是要花钱的，我们假设请 $i$ 号 MM 吃饭要花 $rmb[i]$ 块大洋。而希望骗 MM 当自己 GF 是要费人品的，我们假设请第 $i$ 号 MM 吃饭试图让她当自己 GF 的行为（不妨称作泡该 MM）要耗费 $rp[i]$ 的人品。而对于每一个 MM 来说，sqybi 都有一个对应的搞定她的时间，对于第 $i$ 个 MM 来说叫做 $time[i]$。sqybi 保证自己有足够的魅力用 $time[i]$ 的时间搞定第 $i$ 个 MM ^_^。

sqybi 希望搞到尽量多的 MM 当自己的 GF，这点是毋庸置疑的。但他不希望为此花费太多的时间（毕竟七夕赛的题目还没出），所以他希望在保证搞到 MM 数量最多的情况下花费的总时间最少。

sqybi 现在有 $m$ 块大洋,他也通过一段时间的努力攒到了 $r$ 的人品（这次为模拟赛出题也攒 rp 哦~~）。他凭借这些大洋和人品可以泡到一些 MM。他想知道，自己泡到最多的 MM 花费的最少时间是多少。

注意 sqybi 在一个时刻只能去泡一个 MM ——如果同时泡两个或以上的 MM 的话，她们会打起来的…

输入格式

输入的第一行是 $n$，表示 sqybi 看中的 MM 数量。

接下来有 $n$ 行，依次表示编号为 $1, 2, 3, \ldots , n$ 的一个 MM 的信息。每行表示一个 MM 的信息，有三个整数：$rmb$，$rp$ 和 $time$。

最后一行有两个整数，分别为 $m$ 和 $r$。

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

提示

sqybi 说：如果题目里说的都是真的就好了…

sqybi 还说，如果他没有能力泡到任何一个 MM，那么他就不消耗时间了（也就是消耗的时间为 $0$），他要用这些时间出七夕比赛的题来攒 rp…

【数据规模】

对于 $20 \%$ 的数据，$1 \le n \le 10$；
对于 $100 \%$ 的数据，$1 \le rmb \le 100$，$1 \le rp \le 100$，$1 \le time \le 1000$。
对于 $100 \%$ 的数据，$1 \le m, r, n \le 100$。

题解

题目解析

这道题分为两个解决方向, 一个是次要性背包, 一个是开两个二维背包.

先是介绍第一个方法:洛谷链接

次要性dp是指，在使得一个条件到达最优的情况下，让第二个条件也达到最优，在第二个条件也达到最优时，让第三个条件也最优…

这种分先后次序（或者说分主次）依次达成最优解的动态规划，被称为 次要性dp
确定优化目标

本题的优化目标有两个
1. 让xx的女朋友最多
2. 让xx在女朋友最多的情况下，花费时间最少
我们可以设xx最后的女朋友数最后为 $a$，xx最后花费的时间为 $t$, 则我们可以把最小化目标定为

其中 $M$ 是一个很大的正整数

你一定会问，为什么要这么干？

你可以想象成一个百分比：
- xx的女朋友数对答案的影响为 $p\%$
- xx的花费时间对答案的影响为 $k\%$
在这道题目里xx的女朋友个数对答案的影响比xx的花费时间对答案的影响大的多（或者说起决定性作用）因此，我们要确保xx的女朋友数对答案的影响的百分比 远大于 xx的花费时间对答案的影响

事实上，你只需要确保

这样，当a不同的时候，a对答案起决定性作用，只有当a相同的时候，t 才会对答案起决定性作用

最后结果就是

第二个方法是开两个二维数组:

dpt[i][j]=满足rmb=i,rp=j所最少需要的时间, dpn[i][j]=满足rmb=i,rp=j所最多可以在一起的人

然后我们就开始考虑状态转移方程:

我们有几个目标
- 让女朋友足够多
- 让时间足够少
依照这两点, 我们可以想出来: 当女朋友可以再多谈一个的时候, 我们选择不考虑时间问题,先谈了再说. 于是顺手把dpt的时间加上.当无法再多谈女朋友的时候,我们选择挑一挑, 选择耗时最少的女朋友替换掉之前谈的(我只能对这种操作打666).

AC代码

方法1

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define MOD(size) const long long MOD = size
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(i,a,n) for(int i=a;i<=n;++i)
#define fb(i,a,n) for(int i=a;i>=n;--i)
#define T_ int T;cin >> T;while(T--)
typedef pair<int,int> PII;
typedef long long ll;
typedef long double lb;
typedef unsigned long long ull;

MAXN(1e3);
ll dp[MAXN][MAXN],rmb[MAXN],rp[MAXN],times[MAXN];

signed main(){
	CIN_;CIN;
	ll n,m,r;
	cin >> n;
	fa(i,1,n) cin >> rmb[i] >> rp[i] >> times[i];
	cin >> m >> r;
	fa(i,1,n){
		fb(j,m,rmb[i]){
			fb(k,r,rp[i]){
				dp[j][k] = max(dp[j][k],dp[j-rmb[i]][k-rp[i]]+114514-times[i]);
			}
		}
	}
	cout << (dp[m][r]/114514+1)*114514-dp[m][r] << endl;
	return 0;
}

方法2

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define MOD(size) const long long MOD = size
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(i,a,n) for(int i=a;i<=n;++i)
#define fb(i,a,n) for(int i=a;i>=n;--i)
#define T_ int T;cin >> T;while(T--)
typedef pair<int,int> PII;
typedef long long ll;
typedef long double lb;
typedef unsigned long long ull;

MAXN(1e3);
int dpt[MAXN][MAXN],dpn[MAXN][MAXN],rmb[MAXN],rp[MAXN],times[MAXN];

signed main(){
	CIN_;CIN;
	int n,m,r;
	cin >> n;
	fa(i,1,n) cin >> rmb[i] >> rp[i] >> times[i];
	cin >> m >> r;
	fa(i,1,n){
		fb(j,m,rmb[i]){
			fb(k,r,rp[i]){
                // 如果能泡到更多妹子 
				if(dpn[j][k] < dpn[j-rmb[i]][k-rp[i]] + 1){
					dpn[j][k] = dpn[j-rmb[i]][k-rp[i]] + 1;
					dpt[j][k] = dpt[j-rmb[i]][k-rp[i]] + times[i];
                // 如果能泡到同样多的妹子，选择时间最少的方案 
				}else if(dpn[j][k] == dpn[j-rmb[i]][k-rp[i]] + 1){
					dpt[j][k] = min(dpt[j][k],dpt[j-rmb[i]][k-rp[i]]+times[i]);
				}
			}
		}
	}
	cout << dpt[m][r] << endl;
	return 0;
}