• 周四. 4月 25th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

#01背包#洛谷 2340 [USACO03FALL]Cow Exhibition G

admin

11月 28, 2021

题目

(n)个物品,对于第(i)个物品,
有两种属性,第一种属性为(x_i),第二种属性为(y_i)
问选择若干个物品使得(sum{x_j}geq 0)(sum{y_j}geq 0)的情况下,
(sum{x_j+y_j})最大,(nleq 400)


分析

(dp[x])表示选择第一种属性和为(x)时能取得的最大的(y)
直接平移下标跑01背包即可,最后求最大值


代码

#include <cstdio>
#include <cctype>
#include <cstring>
#define rr register
using namespace std;
int f[800011],n,ans;
inline signed iut(){
	rr int ans=0,f=1; rr char c=getchar();
	while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans*f;
}
inline void Max(int &a,int b){a=a>b?a:b;}
signed main(){
	memset(f,0xcf,sizeof(f)),
	n=iut(),f[n*1000]=0;
	for (rr int i=1;i<=n;++i){
		rr int w=iut(),c=iut();
		if (w<0)
		    for (rr int j=-w;j<=n*2000;++j)
			    Max(f[j+w],f[j]+c);
		else for (rr int j=n*2000;j>=w;--j)
		    Max(f[j],f[j-w]+c);
	}
	for (rr int i=n*1000;i<=n*2000;++i)
	    if (f[i]>=0) Max(ans,i-n*1000+f[i]);
	return !printf("%d",ans);
}

《#01背包#洛谷 2340 [USACO03FALL]Cow Exhibition G》有一个想法
  1. Wow, marvelous blog format! How long have you been blogging for?
    you make running a blog look easy. The whole look
    of your web site is fantastic, let alone the content! You can see similar here e-commerce

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注