EOJ3544 小迷妹在哪儿

 

本题与背包问题有些不同，主要记一下不同之处。

• 背包问题通常直接给出了物品的价值，我们要选择的只是选/不选。然而本题并未给出各个迷妹的价值，有人可能会认为这分数 $a_i$ 就是价值，但显然每个人的价值还会受到追她的时间影响，例如，有个迷妹 A 为(100,1100),即分数100，耗时1100；迷妹 B 为(100,11)，这两者分数相同，B的耗时更少，显然 B 的价值更大，换句话说，选B的收益更大。

   

  在本题中，还要考虑性价比的存在。

   

• 另一点不同在于，背包问题，尤其是01背包，选择的先后顺序与最后结果无关，在01背包中，选总价值相同的一些物品，不管是什么顺序选，最后背包中的总和是一样的，而本题不同，本题先选性价比高的比先选性价比低的更赚，这就是本题需要贪心的地方。

   

因此，需要先确定一个评判价值的标准，根据价值判断是否选择，以及选择顺序先后。由经验知，价值应该与分数正比，与耗时反比，因此猜测： 性价比=分数/耗时；

以下证明：

假设两人为$(a_1,t_1) , (a_2,t_2)$ , 假设她们的性价比相同，也就是说先找A或先找B的得分相同。

设找之前剩余时间 t 。

则

$$(t-t_1)a_1+(t-t_1-t_2)a_2=(t-t_2)a_2+(t-t_2-t_1)a_1$$

化简得

$$t_1a_2=t_2a_1$$

 

$$\frac{a_1}{t_1}=\frac{a_2}{t_2}$$

即两人性价比相同等价于两人（分数/耗时）相同，则性价比可等价于分数/耗时。符合猜想。

 

至此，价值确定了，排序就可以确定，确定顺序之后就是普通的背包问题。

 

总结一下：

 对于类似于背包的DP：

 若题中直接给出的 “价值” 与某种 “消耗” 有关，如相同的分数，不同的耗时，导致 实际价值 不同，则要考虑 性价比 。

 

代码：

 二维DP数组：

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
const int maxt = 305;
struct nd
{
	int a, t;
}arr[maxn];
bool cmp(nd u,nd v) {
	return u.a*v.t > u.t*v.a;
}
int dp[maxn][maxt];
int main() {
	int n, T;
	cin >> n >> T;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i].a >> arr[i].t;
	}
	sort(arr+1, arr + n+1, cmp);
	//选完第i个后剩余时间j
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <=T-arr[i].t; j++) {
			dp[i][j] = max(dp[i-1][j], dp[i-1][j + arr[i].t]+j*arr[i].a);
		}
		for (int j = T - arr[i].t + 1; j <= T; j++)dp[i][j] = dp[i - 1][j];
		for (int j = T; j >=0; j--) dp[i][j] = max(dp[i][j], dp[i][j + 1]);
	}
	int ans = 0;
	for (int i = 0; i <= T; i++) {
		ans = max(ans, dp[n][i]);
	}
	cout << ans;
	return 0;
}

 一维DP数组：

 一维数组滚动时，注意更新的顺序，是从左往右还是从右往左，否则可能此轮更新时应使用上轮数据，却用了此轮的数据。

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
struct nd
{
	int a, t;
}arr[maxn];
bool cmp(nd u,nd v) {
	return u.a*v.t > u.t*v.a;
}
int dp[305];
int main() {
	int n, T;
	cin >> n >> T;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i].a >> arr[i].t;
	}
	sort(arr+1, arr + n+1, cmp);
	//选完第i个后剩余时间j
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <=T-arr[i].t; j++) {
			dp[j] = max(dp[j], dp[j + arr[i].t]+j*arr[i].a);
		}
		for (int j = T; j >=0; j--) dp[j] = max(dp[j], dp[j + 1]);
	}
	cout << dp[0];
	return 0;
}