洛谷 P8742题解

这篇具有很好参考价值的文章主要介绍了洛谷 P8742题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

简单版(P2347)传送门

原题传送门

有一道类似的题目(P2347),先扯一扯~


1.P2347

题目分析

动态规划入门题(01背包可行性问题)~

我们 \(dp_j\) 为能否用砝码称出 \(j\) 重量,1 为可以,0 为不可以

  • 为了转移,\(dp_{_{0}} \gets 1\)什么都不放时,重量为 0,因此可以称出。

那么枚举 \(dp_{_{1}} \sim dp_{sum}(sum\) 为砝码可称出的最大重量\()\)

  • 如果 \(j-w\) 可以称出,且重量为 \(w\) 的砝码存在未超出个数限制,则 \(j\) 可以称出。即 \(dp_j = dp_{j - w}(j - w \geqslant 0)\)

那么动态转移方程显而易见:

  • \(dp_j = dp_{ j - a_i \times k} (j - a_i \times k \geqslant 0 , k \leqslant b_i)\)

PS:\(a_i\):砝码 \(i\)重量\(b_i\):砝码 \(i\) 有的个数

代码

#include<bits/stdc++.h>
using namespace std;
int n = 6, ans = 0, sum = 0;
int dp[1100], a[10] = {0, 1, 2, 3, 5, 10, 20}, b[200];
int main()
{
	fill(dp, dp + 1100, 0);
	for (int i = 1; i <= n; i++) cin >> b[i], sum += a[i] * b[i];
	dp[0] = 1;
	for (int i = 1; i <= n; i++){
		for (int j = sum; j >= 0; j--){ //反着来,不然会重复
			for (int k = 1; k <= b[i]; k++){ 
				if (dp[j - a[i]*k] == 1 and j - a[i]*k >= 0 and dp[j] == 0)
					dp[j] = 1,ans++;
			}
		}
	}

	cout << "Total=" << ans;
	return 0;
}

2.P8742

题目分析

因为砝码可以放另一边,即减去这个砝码的重量,所以反着还要再来遍历一遍。

如果 \(dp[j] + a[i] = 1\) 那么 \(dp[j] \gets 1\)

转移方程:

  • \(dp_j = dp_{ j - a_i } (j - a_i \geqslant 0)\)

  • \(dp_j = dp_{ j + a_i } (j + a_i \leqslant sum)\)文章来源地址https://www.toymoban.com/news/detail-460825.html

代码

#include <bits/stdc++.h>
using namespace std;
int dp[100010], a[110];
long long sum = 0, ans = 0;
int main()
{
	int n;
	cin >> n;
	fill(dp, dp + 100010, 0);
	dp[0] = 1;
	for (int i = 0; i < n; i++)
		cin >> a[i], sum += a[i];
	for (int i = 0; i < n; i++){
		for (int j = sum; j >= a[i]; j--){ //优化,不枚举i<a[j]的情况
			if (dp[j - a[i]] == 1 and dp[j] != 1)
				dp[j] = 1, ans++;
		}
	}
	for (int i = 0; i < n; i++){
		for (int j = 1; j <= sum - a[i]; j++){ //同理
			if (dp[j + a[i]] == 1 and dp[j] == 0)
					dp[j] = 1, ans++;
		}
	}
	cout << ans;
	return 0;
}

到了这里,关于洛谷 P8742题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 洛谷 P1122 最大子树和 题解

    一道入门的树形DP。 首先我们对于数据进行有序化处理,这便于我们利用数据结构特点(可排序性)来发觉数据性质(有序、单调、子问题等等性质),以便于后续的转化、推理和处理。 有序化可以“转化和创造”性质 首先将视角从无根树切换为有根树,这样我们就可以得

    2024年02月17日
    浏览(32)
  • 洛谷 P1336 最佳课题选择 题解

    题目链接 状态:考虑 (f_{i,j}) 表示前 (i) 种论文里面,一共写了 (j) 篇,的最少花费时间。 转移策略:我们一次考虑每一种论文写多少篇。假设写 (k) 篇, (k in [0,j] cap mathbb{Z}) ,有转移方程: [f_{i,j} = min(f_{i-1,j-k} + text{cost}(i,k)), k in [0,j] cap mathbb{Z}] 其中 [text{

    2024年02月14日
    浏览(36)
  • 洛谷 P1387 最大正方形 题解

    通过二维前缀和判定矩形内是否全为1,计算和等于长度的平方就判断为是 复杂度 (Theta (n^2log{n})) 设状态 (f_{i,j}) 为以第 (i) 行 (j) 列为右下角的最大正方形的边长, (a_{i,j}) 表示输入矩阵中的数值,有转移方程: [f_{i,j} = (min(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}) + 1) * a_{i,j}] 解释:

    2024年02月16日
    浏览(43)
  • 洛谷 P3304 [SDOI2013] 直径 题解

    题目链接 第一部分好说,求直径,dfs或者DP都可以。 第二部分,有一个定理,就是所有直径中点重叠。 那么有两种情况 一种是中点在一个节点上,那么显然这个点是每条直径的终点,也就是说直径的一半相等。从这个点出发dfs,找出所有最远点。如果只有两条,输出depth之

    2024年02月14日
    浏览(37)
  • 【洛谷题解】B2010 带余除法

    题目链接:带余除法 - 洛谷 题目难度:入门 涉及知识点:除法,计算余数 题意: 分析:计算商后再用a/商*b得余数 AC代码: 总结:计算商后再用a/商*b得余数

    2024年02月19日
    浏览(34)
  • 洛谷 P1379 八数码难题 A* 题解

    刚做完一道模板A*,看到这题我直接小脑萎缩了... 阿米诺斯!这怎么用A*?!——刚开题的我 beeeeeeeeee like 甚至比模板简单(这是绿的...) 其实会是会但是纸张的是这玩意我不会搞估价函数我草! 然后突然想到能不能把这个状态下有多少个数字不在目标位置作为估价函数?

    2024年03月22日
    浏览(60)
  • 【洛谷 P2084】进制转换 题解(模拟+字符串)

    无 今天小明学会了进制转换,比如(10101)2 ,那么它的十进制表示的式子就是 : 1*2 4+0*2 3+1*2 2+0*2 1+1*2^0, 那么请你编程实现,将一个M进制的数N转换成十进制表示的式子。 注意:当系数为0时,该单项式要省略。 两个数,M和N,中间用空格隔开。 共一行,一个十进制表示的式

    2024年01月20日
    浏览(35)
  • 【洛谷 P1996】约瑟夫问题 题解(数组+模拟+循环)

    n n n 个人围成一圈,从第一个人开始报数,数到 m m m 的人出列,再由下一个人重新从 1 1 1 开始报数,数到 m m m 的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。 注意:本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 n − 1

    2024年02月07日
    浏览(34)
  • 【洛谷 P1106】删数问题 题解(贪心+字符串)

    键盘输入一个高精度的正整数 N N N (不超过 250 250 250 位),去掉其中任意 k k k 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 N N N 和 k k k ,寻找一种方案使得剩下的数字组成的新数最小。 输入两行正整数。 第一行输入一个高精度的正整数 n n

    2024年02月07日
    浏览(42)
  • 【洛谷 P1181】数列分段 Section I 题解(贪心算法)

    对于给定的一个长度为 N N N 的正整数数列 A i A_i A i ​ ,现要将其分成 连续 的若干段,并且每段和不超过 M M M (可以等于 M M M ),问最少能将其分成多少段使得满足要求。 第1行包含两个正整数 N , M N,M N , M ,表示了数列 A i A_i A i ​ 的长度与每段和的最大值,第 2 2 2 行包

    2024年02月08日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包