poj 2184 Cow Exhibition dp

缘起

日常浪费生命 poj 2184 Cow Exhibition 本题阔以视作是01背包的变种——应用了01背包的思想.

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
告诉你n头牛的智商和幽默感，要求出智商之和与幽默感之和的和的最大值，其中这两个和都不能为负。

【输入】
第一行就是一个n(1 <= N <= 100),表示牛的数目,后面n行,每行两个数字 s和f 表示智商和幽默感
-1000 <= S,F <= 1000

【输出】
智商之和+幽默感之和的最大值. 注意, 智商之和和幽默感之和都需要>=0

【样例输入】
5
-5 7
8 -6
6 -3
2 1
-8 -5

【样例输出】
8

【限制】
1s

【hint】
Bessie chooses cows 1, 3, and 4, giving values of TS = -5+6+2 = 3 and TF 
= 7-3+1 = 5, so 3+5 = 8. Note that adding cow 2 would improve the value 
of TS+TF to 10, but the new value of TF would be negative, so it is not 
allowed.

依旧是dp. 这种题目好像在qq群里面被问到过

1
2
3
4
5
6
7
8
9
10
11
令 dp[i][j]=只考虑前i头牛的取用时，ai之和为j的时候, bi们的和的最大值.
但是注意, ai之和可能为负数, 但是最负不可能小于-1000*100=-10w, 所以简单做1个技术处理即可,即
令dp[i][j]=只考虑前i头牛的取用时, ai之和+100005=j时, bi们的最大值.
则
dp[i][j] = max{dp[i-1][j], dp[i-1][j-ai]+bi}, 1<=i<=n, 0<=j<=200000
也就是考虑第i头牛取与不取. 其实和01背包是一样的, 滚动掉i 得到
dp[j] = max{dp[j], dp[j-ai]+bi}, 0<=j<=200000
此dp方程进行n次即可.
初始化值是不考虑任何牛的取用时,
dp[100005]=0, 其余 dp[j]们为 -inf
答案就是最后dp[j]（j>=100005）中 j+dp[j]的最大值.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

const int inf = 0x3f3f3f3f, os = 100005;
int n,dp[os<<1];

void zp(int s, int f) // 01背包,要注意,不能只会套01背包的模板, 还要理解01背包的思想精髓
{
	if (s>=0) // 注意, 因为是01背包,所以要注意dp的顺序. s>=0的话,就是从大到小才能保证至多取1件
	{
		for (int j = (os<<1)-1; j>=s; j--)
		{
			dp[j] = max(dp[j], dp[j-s]+f);
		}
	}
	else // s<0的话, 就是从小到大才能保证至多取1件. 
	{
		for (int j = 0; j<(os<<1)+s; j++)
		{
			dp[j] = max(dp[j], dp[j-s]+f);
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	for (int i = 0; i<(os<<1); i++)
	{
		dp[i] = -inf;
	}
	dp[os] = 0; // 初始化
	for (int i = 1,s,f; i<=n;i++)
	{
		scanf("%d%d", &s, &f);
		zp(s,f); // 读入一个牛的数据, 就进行一次01背包
	}
	int ans = 0;
	for (int j = os; j<(os<<1); j++)
	{
		if (dp[j]>=0)
		{
			ans = max(ans, j-os+dp[j]);
		}
	}
	printf("%d\n", ans);
	return 0;
}

ac情况（好慢~ 水过~）

Status Accepted
Time 313ms
Memory 868kB
Length 823
Lang C++
Submitted 2019-08-29 08:26:46
Shared
RemoteRunId 20814367