P1509 找啊找啊找GF

次要性动态规划

概念

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

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

思路

确定优化目标

让女朋友最多。
在女朋友最多的情况下，花费时间最少。

设定最小化目标

设最后的女朋友数最后为$ a$ ，最后花费的时间为$t$

则我们可以把最小化目标定为

$M \times a - t$

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

可以类比百分比理解。

女朋友数对答案的影响为$\%p$

花费时间对答案的影响为 $\%k$

在这道题目里女朋友个数对答案的影响

比花费时间对答案的影响大的多

因此，我们要确保女朋友数对答案的影响的百分比 远大于 花费时间对答案的影响

事实上，只需要确保

$M > 所有的花费费的时间总和t_{max}$

这样，当$a$不同的时候，$a$对答案起决定性作用，

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

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 101;
int n, m, r;
int rmb[N], rp[N], tim[N];
int F[N][N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> rmb[i] >> rp[i] >> tim[i];
		tim[i] = 20000 * 1 - tim[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--)
			{
				F[j][k] = max(F[j][k], F[j - rmb[i]][k - rp[i]] + tim[i]);
			}
		}
	}
	cout << ((F[m][r] / 20000) + 1) * 20000 - F[m][r];
	return 0;
}

双动态规划维护

思路

设置两个状态，一个表示最多女朋友数，一个表示最小时间。

利用更新最多女朋友数来判断是否更新最小时间。

实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 101;
int n, m, r;
int rmb[N], rp[N], tim[N];
int F[N][N], T[N][N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> rmb[i] >> rp[i] >> tim[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 (F[j][k] < F[j - rmb[i]][k - rp[i]] + 1)
				{
					F[j][k] = F[j - rmb[i]][k - rp[i]] + 1;
					T[j][k] = T[j - rmb[i]][k - rp[i]] + tim[i];
				}
				else if (F[j][k] == F[j - rmb[i]][k - rp[i]] + 1)
				{
					T[j][k] = min(T[j][k],  T[j - rmb[i]][k - rp[i]] + tim[i]);
				}
			}
		}
	}
	cout << T[m][r];
	return 0;
}