首页 > 编程语言 >papamelon 344. 奶牛展览 Cow Exhibition(挑战程序设计竞赛) dp

papamelon 344. 奶牛展览 Cow Exhibition(挑战程序设计竞赛) dp

时间:2023-06-12 14:44:35浏览次数:50  
标签:newZero const Cow int 情商 344 ans papamelon dp

地址 https://www.papamelon.com/problem/344

贝西有权选择让哪些奶牛参加展览。
由于负的智商或情商会造成负面效果,所以贝西不希望出展奶牛的智商之和小于零,或情商之和小于零。
满足这两个条件下,她希望出展奶牛的智商与情商之和越大越好,请帮助贝西求出这个最大值。

输入
第一行:单个整数 
1≤N≤100
第二行到第 N+1 行:第 
i+1 行有两个整数:
Si 和 Fi,表示第 i 奶牛的智商和情商,
−1000≤Si,Fi≤1000
输出
一个整数:表示情商与智商和的最大值
贝西可以不让任何奶牛参加展览,如果这样做是最好的,输出 
0
样例 1
输入
5
-5 7
8 -6
6 -3
2 1
-8 -5
输出
8

解答
很明显的背包问题
但是在数据范围上好多细节
一个是背包的空间太大,需要做空间优化
一个是背包的索引有的是负值。
我们定义dp[i][j] 表示前i个牛的情商为j的情况下最大的智商为多少
然后偏移j的索引为 最大可能负值的一半,也就是100个牛情商全为负数的情况下, maxIdx = 100*-1000/2

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;

const int N = 20010;
const int M = 110;
const int newZero = 10000;

int dp[M][N];
int n;
int arr[M][2];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i][0] >> arr[i][1]; 
	}

	memset(dp, -0x3f, sizeof dp);
	dp[0][newZero] = 0;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < N; j++) {
			dp[i][j] = dp[i - 1][j];
			int eq = arr[i][0]; int iq = arr[i][1];

			if(j-eq <N)
				dp[i][j] = max(dp[i][j], dp[i - 1][j - eq] + iq);


			if (i == n && j >= newZero && dp[n][j] >= 0) {

				if (ans < j + dp[i][j] - newZero) {
					//printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);
				}
				ans = max(ans, j + dp[i][j] - newZero);
				
			}
		}
	}

	cout << ans << endl;

	return 0;
}

能过部分数据 但是回报空间过大,这时候我们需要做空间优化
使用滚动数组解决空间问题

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;


const int N = 200010;
const int M = 110;
const int newZero = 100000;

int dp[2][N];
int n;
int arr[M][2];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i][0] >> arr[i][1]; 
	}

	memset(dp, -0x3f, sizeof dp);

	for (int i = 0; i < N; i++) {
		dp[0][i] = -999999999;
		dp[1][i] = -999999999;
	}

	dp[0][newZero] = 0;
	int ans = 0;
	int curr = 1; int prev = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < N; j++) {
			dp[curr][j] = dp[prev][j];
			int eq = arr[i][0]; int iq = arr[i][1];

			if(j-eq <N)
				dp[curr][j] = max(dp[curr][j], dp[prev][j - eq] + iq);


			if (i == n && j >= newZero && dp[curr][j] >= 0) {
				ans = max(ans, j + dp[curr][j] - newZero);
			}
		}
		swap(curr, prev);
	}

	cout << ans << endl;

	return 0;
}

视频题解空间

标签:newZero,const,Cow,int,情商,344,ans,papamelon,dp
From: https://www.cnblogs.com/itdef/p/17475002.html

相关文章

  • HDU 2838 Cow Sorting(树状数组)
    题意:首先每次只能交换相邻的两头牛,并且最后要求升序排列,所以最后整个序列的逆序是0,每次交换只可以消除1个逆序。(令a[i]的逆序是从1到i-1比它大的数的个数。)思路:对于某个数,要把它变成有序的,那么很容易可以推算出公式就是它自身的逆序数乘自身的值再加上它的逆序数的和,自己算算看看。......
  • papamelon 349. 城市帮派 Find them, Catch them(挑战程序设计竞赛)
    地址https://www.papamelon.com/problem/349一个城市里有两个帮派,另外有N个成员,成员从1∼N进行编号,每个成员来自于其中一个帮派。给定M个信息,每个信息有两种格式:Dab:a,b(1≤a,b≤N,a≠b)两个人不是一个帮派的Aab:判断a,b(1≤a,b≤N,a≠b)两个人是否为同一个帮派......
  • papamelon 348. 修复网络 Wireless Network(挑战程序设计竞赛)
    地址https://www.papamelon.com/problem/348给定N台电脑,它们分别落在地图上的坐标xi,yi上。现在它们都损坏了。我们准备修复其中的某一些电脑。当一台电脑修复好了后,它和其他相距不超过距离d的正常电脑就可以通信。通信具有传递性:A和B能通信,B和C能通信,那么......
  • P3087 [USACO13NOV]Farmer John has no Large Brown Cow S
    正解像是康托展开之类的?但是蒟蒻不会,所以用了一堆STL。对于每一列的字符串,按照字典序给它们编号。这样每一行的形容词串就变成了一堆数字。设共有\(s\)列,第\(i\)列共有\(b_i\)个不同的形容词,那么实际上每一行就是一个“第\(i\)位是\(b_i\)进制”的数。设第\(j\)行......
  • (输出路径搜索)[USACO06OCT] Cows on Skates G
    题目描述本题使用SpecialJudge。FarmerJohn把农场划分为了一个 r 行 c 列的矩阵,并发现奶牛们无法通过其中一些区域。此刻,Bessie位于坐标为 (1,1)(1,1) 的区域,并想到坐标为 (,)(r,c) 的牛棚享用晚餐。她知道,以她所在的区域为起点,每次移动至相邻的四个区域之一,总有......
  • [USACO09MAR]Cow Frisbee Team S
    [USACO09MAR]CowFrisbeeTeamS题目描述老唐最近迷上了飞盘,约翰想和他一起玩,于是打算从他家的\(N\)头奶牛中选出一支队伍。每只奶牛的能力为整数,第\(i\)头奶牛的能力为\(R_i\)。飞盘队的队员数量不能少于\(1\)、大于\(N\)。一支队伍的总能力就是所有队员能力的总和。约......
  • leetcode 344. Reverse String
    Writeafunctionthattakesastringasinputandreturnsthestringreversed.Example:Givens="hello",return"olleh".classSolution(object):defreverseString(self,s):""":types:str......
  • Tallest Cow(最高的牛)poj3263
    题目描述:FJ'sN(1≤N≤10,000)cowsconvenientlyindexed1..Narestandinginaline.Eachcowhasapositiveintegerheight(whichisabitofsecret).YouaretoldonlytheheightH(1≤H≤1,000,000)ofthetallestcowalongwiththeindexIoftha......
  • P9344 去年天气旧亭台 代码
    不带滚动数组代码:#include<iostream>#include<cstdio>#include<cstring>#defineintlonglongusingnamespacestd;constintN=2000010;inta[N],c[N],T,n,f[N];signedmain(){ scanf("%lld",&T); while(T--){ mems......
  • 洛谷 P9344. 去年天气旧亭台
    去年天气旧亭台题目背景依旧是过往的天气,过往的楼台烟雨。时间悄悄流逝着,山河仍在,人却已不是过去的人……题目描述登上楼台,旧时满面沉灰的地板映入眼帘。共有$n$块地板,地板分为两类,第$i$块地板的类别用$c_i$表示,积灰程度用$a_i$表示。注意$c_i$为$0$或$1$。现......