首页 > 其他分享 >2023年牛客基础训练营4-D

2023年牛客基础训练营4-D

时间:2023-03-29 12:22:25浏览次数:49  
标签:pre suf int max 训练营 long 牛客 2023 dp

题目链接:https://ac.nowcoder.com/acm/contest/46812/D

思路:01背包,当要从一段物品中选一件出来,可以像前缀和和后缀和一样,进行前缀dp和后缀dp。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
long long dp[N],dpp[N];
long long pre[N][N],suf[N][N];
long long cnt[N];
int w[N],v[N];
int main(){
	int n,m;
	cin>>n>>m;
	cnt[0] = 1;
	for (int i=1;i<=n;i++) cin>>v[i]>>w[i];
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			pre[i][j] = pre[i-1][j];
			if (j>=v[i]) pre[i][j] = max(pre[i][j],pre[i-1][j-v[i]]+w[i]);
		}
	}
	for (int i=n;i>=1;i--){
		for (int j=1;j<=m;j++){
			suf[i][j] = suf[i+1][j];
			if (j>=v[i]) suf[i][j] = max(suf[i][j],suf[i+1][j-v[i]]+w[i]);
		}
	}
    for (int k=1;k<=n;k++){
        long long val = 0,val2 = 0;
        for (int i=0;i<=m;i++){
            val = max(val,pre[k-1][i]+suf[k+1][m-i]);
            if (m-v[k]>=i) val2 = max(val2,pre[k-1][i]+w[k]+suf[k+1][m-v[k]-i]);
        }
        long long ans = max(0LL,val+1-val2);
        cout<<ans<<'\n';
    }
	return 0;
}

标签:pre,suf,int,max,训练营,long,牛客,2023,dp
From: https://www.cnblogs.com/xjwrr/p/17268468.html

相关文章

  • 2023年牛客基础训练营4-J
    题目链接:https://ac.nowcoder.com/acm/contest/46812/J大致题意:给你一些大小关系,要你判断有些点是否可以判断他的具体位置。易错点:将这个图用拓扑图的做法来思考,陷入思维......
  • 2023年牛客基础训练营3-K
    题目链接:https://ac.nowcoder.com/acm/contest/46811/K需要的知识:质因子公式。介绍:如果一个数可以化为\(i^x*j^y*k^z\),则这个数的因子个数为:\((x+1)*(y+1)*(z+1)\),......
  • TopSolid 2023 v7.17 Multilingual edition full licensed
     T opSolid'Design2023在设计、钢材、模具和电极方面增加了近400项新功能: ·    逼真渲染模块已得到改进,引入了几个允许高质量逼真渲染的主要新功能。......
  • 2023.3.29每日总结
    今天学习了运用jsp实现在线的视频播放0.MP4格式主代码:<body><videowidth="320"height="240"controls="controls"><sourcesrc="zp.mp4"type="video/......
  • 不坑盒子 V2023.0325 && 打工人插件 大众实用型办公高效利器。
    不坑盒子这是一个非常好用的插件工具,专门应用在Word文档和wps,支持Office2010以上的版本,操作也简单且实用。不坑盒子下载及使用说明 一键排版功能像是下面的自动排版......
  • 2023-03-29 图的深度优先遍历
    图的深度优先遍历1数据结构遍历的意义每种数据结构,都必须有遍历的方式很多算法的本质都是遍历,对于图论问题,真正理解遍历,已经可以应付80%的问题了树的遍历复习复......
  • 总结20230328
    今天周二,上了实用英语阅读与翻译、数据库原理、python程序设计。实用英语阅读与翻译讲的是词类转换。数据库原理讲的是第五章和第六章的一部分,具体第五章讲的是视图,第六......
  • 2023/3/28
      今天的工作很少~也很多:依赖冲突。对于gradle系统出现的依赖冲突,真的很无解。不清楚如何移除。网上的也很难有准确的。除了这些依赖冲突的问题。还写了每个页面的基本......
  • 2023/3/28每日随笔
    今天,上了英语口语,聊的很开心,随后上了数据库,学了视图的建立,感觉视图和表有着相似的关系,视图是表内数据的一种展示形式我认为,你想要什么数据就去展示什么数据,通过select语句,......
  • 2023年3月28日软工日报
    今天完成了外包画界面。干了半天mysql存文件如何实现。好累啊,主要是不会后端如何接受和存取前端文件 ......