当前位置:网站首页>[蓝桥杯2021初赛] 砝码称重
[蓝桥杯2021初赛] 砝码称重
2022-07-06 09:14:00 【%xiao Q】
题目
题目描述
你有一架天平和N 个砝码,这N 个砝码重量依次是W1, W2, … , WN。
请你计算一共可以称出多少种不同的重量?
注意砝码可以放在天平两边。
输入格式
输入的第一行包含一个整数N。
第二行包含N 个整数:W1, W2, W3, … , WN。
对于50% 的评测用例,1 ≤ N ≤ 15。
对于所有评测用例,1 ≤ N ≤ 100,N 个砝码总重不超过100000。
输出格式
输出一个整数代表答案。
输入样例
3
1 4 6
输出样例
10
分析
这道题暴力搜索肯定是会超时的,dfs大概的话,能过50%的点。
这题的正解为dp(奈何菜鸡不会dp),那么接下来就来分析dp的做法:
- 状态表示f[i][j]:表示前i个砝码中选,称出的重量为j的状态,为1表示可以称出,为0则不能称出。
- 状态转移:
- a[i] == j,那么f[i][j]一定可以被称出
- a[i] != j,那么就可以从f[i - 1][j],f[i - 1][abs(j - a[i])](本质为f[i - 1][j - a[i]],为了防止出现负的下标,所以取绝对值),f[i - 1][j + a[i]]这3种情况中转移过来。
f[i - 1][j]:i - 1个砝码能称出的,i个也能称出
f[i - 1][j - a[i]]:加上当前的砝码
f[i - 1][j + a[i]]:减去当前的砝码
满足3种的任意一种,即可判断f[i][j]的重量为j的能否被称出
参考代码1(dfs)---- 过50%的样例(O(3^n))
#include <iostream>
#include <cstdio>
#include <set>
#include <map>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++)
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;
const int N = 110, M = 1e5 + 10;
int n, ans = 0;
int a[N];
bool st[M];
void dfs(int u, int sum)
{
if(!st[sum] && sum > 0) ans++, st[sum] = true;
if(u == n + 1) return ;
dfs(u + 1, sum + a[u]);
dfs(u + 1, sum - a[u]);
dfs(u + 1, sum);
}
int main()
{
cin >> n;
rep(i, 1, n) cin >> a[i];
dfs(1, 0);
cout << ans << endl;
return 0;
}
参考代码2(dp)---- O(nm)
#include <iostream>
#include <cstdio>
#include <set>
#include <map>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++)
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;
const int N = 110, M = 1e5 + 10;
int n, m;
int a[N];
int f[N][M];
int main()
{
cin >> n;
rep(i, 1, n) cin >> a[i], m += a[i];
rep(i, 1, n)
rep(j, 1, m)
{
if(a[i] == j) f[i][j] = 1;
else f[i][j] = f[i - 1][j] | f[i - 1][abs(j - a[i])] | f[i - 1][j + a[i]];
}
int ans = 0;
rep(i, 1, m)
if(f[n][i]) ans++;
cout << ans << endl;
return 0;
}
边栏推荐
- In the era of DFI dividends, can TGP become a new benchmark for future DFI?
- Cookie setting three-day secret free login (run tutorial)
- AcWing 179.阶乘分解 题解
- [recommended by bloggers] C WinForm regularly sends email (with source code)
- Armv8-a programming guide MMU (2)
- Rhcsa certification exam exercise (configured on the first host)
- Generate PDM file from Navicat export table
- [Thesis Writing] how to write function description of jsp online examination system
- MySQL完全卸载(Windows、Mac、Linux)
- Some problems in the development of unity3d upgraded 2020 VR
猜你喜欢
CSDN question and answer module Title Recommendation task (II) -- effect optimization
Copie maître - esclave MySQL, séparation lecture - écriture
打开浏览器的同时会在主页外同时打开芒果TV,抖音等网站
[recommended by bloggers] C # generate a good-looking QR code (with source code)
Django running error: error loading mysqldb module solution
Navicat 導出錶生成PDM文件
QT creator create button
Other new features of mysql18-mysql8
Windows cannot start the MySQL service (located on the local computer) error 1067 the process terminated unexpectedly
Invalid global search in idea/pychar, etc. (win10)
随机推荐
CSDN question and answer tag skill tree (II) -- effect optimization
[Thesis Writing] how to write function description of jsp online examination system
[BMZCTF-pwn] 11-pwn111111
Ansible实战系列一 _ 入门
Image recognition - pyteseract TesseractNotFoundError: tesseract is not installed or it‘s not in your path
安全测试涉及的测试对象
neo4j安装教程
What does usart1 mean
Postman uses scripts to modify the values of environment variables
01 project demand analysis (ordering system)
数据库高级学习笔记--SQL语句
图片上色项目 —— Deoldify
Picture coloring project - deoldify
Ansible实战系列三 _ task常用命令
Data dictionary in C #
Neo4j installation tutorial
图像识别问题 — pytesseract.TesseractNotFoundError: tesseract is not installed or it‘s not in your path
Ansible practical Series II_ Getting started with Playbook
[C language foundation] 04 judgment and circulation
Why is MySQL still slow to query when indexing is used?