【P2340 [USACO03FALL]Cow Exhibition G】题解

2021年11月24日 阅读数:3
这篇文章主要向大家介绍【P2340 [USACO03FALL]Cow Exhibition G】题解,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题目连接

一道很好的01背包变形题。c++

首先看一眼题很明显能够发现是背包。spa

此题我当时的第一反应是二维费用背包,然而会TLE+MLE,因而打开题解思考01背包作法。code

\(dp_i\) 表明智商和为 \(i\) 时情商的最大值。get

\[dp_i=\max_{j=1}^n(dp_{i-s_j}+f_j) \]

经典的01背包转移。it

最后答案为 \(\max (dp_i+i) (dp_i\geqslant 0,\,i\geqslant 0)\)io

然而咱们发现有些奶牛很蠢,智商为负数,这时候与01背包倒着来不一样,要变成正着来。class

同时因为智商和可能为负,因此要默认加400000。test

Code

// Problem: P2340 [USACO03FALL]Cow Exhibition G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2340
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define M
//#define mo
//#define N
int n, m, i, j, k; 
int dp[800010]; 
int s, f, ans; 

signed main()
{
//	freopen("tiaoshi.in", "r", stdin); 
//	freopen("tiaoshi.out", "w", stdout); 
	memset(dp, 0xAA, sizeof(dp)); 
	dp[400000]=0; 
	n=read(); 
	for(i=1; i<=n; ++i)
	{
		s=read(); f=read(); 
		if(s>=0)
		{
			for(j=800000; j>=s; --j)
				dp[j]=max(dp[j], dp[j-s]+f); 
		}
		else
		{
			for(j=0; j-s<=800000; ++j)
				dp[j]=max(dp[j], dp[j-s]+f); 
		}
	}
	for(i=400000; i<=800000; ++i) 
	{
		if(dp[i]>=0) ans=max(ans, i-400000+dp[i]); 
		// printf("dp(%lld)=%lld\n", i, dp[i]); 
	}
	printf("%lld", ans); 
	return 0; 
}