首页 > 其他分享 >P3985 不开心的金明

P3985 不开心的金明

时间:2023-06-10 09:01:54浏览次数:38  
标签:开心 01 mini P3985 sum min int dp 金明

P3985 不开心的金明

  • 这道题好像是01背包,但价格 \(v[i]\) 是 \(10^9\) 级别的,意味着dp数组的第一维要开到 \(10^9\),显然不可能

  • 题目中说:

对所有的 \(i=1,2,3,…,N\),$ min(v_i) \le v_i \le min(v_i)+3$.

  • 也就是 \(v[i]\) 的最大值最小值的差不大于3,由此想到把每个 \(v[i]\) 减去 \(v[i]_{min} -1\),再按照01背包去做

  • 但是都减去一个数后无法通过一般的01背包的dp数组确定“考虑了前 \(i\) 件物品,总价为 \(j\)”中的 \(j\),所以要把状态表示改变一下

状态表示

\[dp[j][k]表示考虑了前i件物品后(包括当前物品),选了k件物品,减去 v[i]_{min}-1 后的总价为j \]

  • 所以转移方程如下

\[dp[j][k]=max(dp[j][k],dp[j-v[i]][k-1]+p[i]) \]

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e9;

int n,w;
int mini=INF,sum,maxi;
struct Obj{
	int v,p;
}in[101];
int dp[1001][1001];

signed main(){
//	freopen("1.in","r",stdin);
	
	cin>>n>>w;
	for(int i=1;i<=n;i++){
		cin>>in[i].v>>in[i].p;
		sum+=in[i].v;
		mini=min(mini,in[i].v);
	}
	mini--;
	sum-=mini*n;
	for(int i=1;i<=n;i++)
		in[i].v-=mini;
		
	for(int i=1;i<=n;i++){
		for(int j=sum;j>=in[i].v;j--){
			for(int k=1;k<=n;k++){
				if(j+mini*k<=w)
					dp[j][k]=max(dp[j][k],dp[j-in[i].v][k-1]+in[i].p);
			}
		}
	}
	for(int i=1;i<=sum;i++){
		for(int j=1;j<=n;j++)
			maxi=max(maxi,dp[i][j]);
	}
	cout<<maxi<<"\n";
}

标签:开心,01,mini,P3985,sum,min,int,dp,金明
From: https://www.cnblogs.com/wangyangjena/p/17468249.html

相关文章

  • 上万条开心驿站笑话内容ACCESS\EXCEL数据库
    因为签于网站笑话不是采用微博型(一句或两句短篇可以采用250长度的文本型存储),而是所以文章内容型,所以内容保存的字段是MicrosoftAccess数据库里的备注类型。数据库内容经过整理,格式比较统一,比如不会有多余的段落或不整齐的段落;分类比较集中,只有爆笑男女(305)、儿童笑话(594)、夫妻......
  • [NOIP2006 普及组] 开心的金明
    [NOIP2006普及组]开心的金明题目描述金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过\(N\)元钱就行”。今天一早金明就开始做预算,但是他想买的东西太多了......
  • 近万条开心猜灯谜猜谜语ACCESS\EXCEL数据库
    元宵节马上就到了,中国民间素有“观灯猜谜”的习俗,今天再给大家一款猜灯谜的数据,看看有没有朋友喜欢(你需要什么数据如果我网站没有也可以交给我找找)。据记载,猜灯谜自南宋起开始流行,至今不衰。“猜灯谜”又叫“打灯谜”,出现在宋朝。南宋时,首都临安每逢元宵节时制谜、猜谜的人众多......
  • 开心档之C++ Web 编程
    C++Web编程什么是CGI?公共网关接口(CGI),是一套标准,定义了信息是如何在Web服务器和客户端脚本之间进行交换的。CGI规范目前是由NCSA维护的,NCSA定义CGI如下:公共网关接口(CGI),是一种用于外部网关程序与信息服务器(如HTTP服务器)对接的接口标准。目前的版本是CGI/1.1,CGI/......
  • 开心档之C++ 变量类型
    C++变量类型变量其实只不过是程序可操作的存储区的名称。C++中每个变量都有指定的类型,类型决定了变量存储的大小和布局,该范围内的值都可以存储在内存中,运算符可应用于变量上。变量的名称可以由字母、数字和下划线字符组成。它必须以字母或下划线开头。大写字母和小写字母是不......
  • 开心档之C++ 重载运算符和重载函数
    C++重载运算符和重载函数C++允许在同一作用域中的某个函数 和运算符 指定多个定义,分别称为函数重载 和运算符重载。重载声明是指一个与之前已经在该作用域内声明过的函数或方法具有相同名称的声明,但是它们的参数列表和定义(实现)不相同。当您调用一个重载函数 或重载运算符 时......
  • 开心档之MySQL 创建数据库
    MySQL数据类型MySQL中定义数据字段的类型对你数据库的优化是非常重要的。MySQL支持多种类型,大致可以分为三类:数值、日期/时间和字符串(字符)类型。数值类型MySQL支持所有标准SQL数值数据类型。这些类型包括严格数值数据类型(INTEGER、SMALLINT、DECIMAL和NUMERIC),以及近似......
  • 开心档之MySQL 数据类型
    MySQL数据类型MySQL中定义数据字段的类型对你数据库的优化是非常重要的。MySQL支持多种类型,大致可以分为三类:数值、日期/时间和字符串(字符)类型。数值类型MySQL支持所有标准SQL数值数据类型。这些类型包括严格数值数据类型(INTEGER、SMALLINT、DECIMAL和NUMERIC),以......
  • 开心档之MySQL 创建数据库
    MySQL创建数据库我们可以在登陆MySQL服务后,使用create命令创建数据库,语法如下:CREATEDATABASE数据库名;以下命令简单的演示了创建数据库的过程,数据名为RUNOOB:[root@host]#mysql-uroot-pEnterpassword:******#登录后进入终端mysql>createDATABASE......
  • 开心档之C++ 预处理器
    C++预处理器预处理器是一些指令,指示编译器在实际编译之前所需完成的预处理。所有的预处理器指令都是以井号(#)开头,只有空格字符可以出现在预处理指令之前。预处理指令不是C++语句,所以它们不会以分号(;)结尾。我们已经看到,之前所有的实例中都有 #include 指令。这个宏用于把头......