ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[牛客竞赛]蕾凹娜的哀伤(多重背包DP + 二进制优化)

2022年8月3日 125点热度 0人点赞 0条评论

题目传送门:A-蕾凹娜的哀伤_喜迎暑假多校联赛第二场(欢乐AK找回自信) (nowcoder.com)

题意 / Problem

中文题意不解释了。

思路 / Thought

多重背包问题,加上二进制优化后复杂度为O(N * V * log(S))。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e4 + 5;
int dp[maxn];//dp[i] means the Worth could get by Volume i.

signed main()
{
	ios::sync_with_stdio(false);
	int N, V;cin >> N >> V;//the count of Items and the Volume of bag.
	for(int i = 1;i <= N; ++ i)
	{
		int t, w, s;//the Volume, Worth and Count of Items.
		cin >> t >> w >> s;
		//二进制分解
		for(int j = 1;j <= s; s -= j, j <<= 1)//the count of items buy once.
			for(int k = V;k >= j * t; -- k)//remember Traverse from back to front
				dp[k] = max(dp[k], dp[k - j * t] + j * w);

		if(s)//the remainder of items should be calculate too.
		{
			for(int k = V;k >= s * t; -- k)//remember Traverse from back to front
				dp[k] = max(dp[k], dp[k - s * t] + s * w);
		}
	}
	cout << *max_element(dp + 1, dp + 1 + V) << '\n';
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ DP 二进制 动态规划 多重背包 牛客网 算法竞赛 背包
最后更新:2022年8月3日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题意 / Problem
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号