当前位置:网站首页>[Bluebridge cup 2021 preliminary] weight weighing
[Bluebridge cup 2021 preliminary] weight weighing
2022-07-06 11:26:00 【%xiao Q】
subject
Title Description
You have a balance and N A weight , this N The weights of the weights are W1, W2, … , WN.
Please calculate how many different weights you can weigh ?
Note that the weight can be placed on both sides of the balance .
Input format
The first line of input contains an integer N.
The second line contains N It's an integer :W1, W2, W3, … , WN.
about 50% The evaluation case of ,1 ≤ N ≤ 15.
For all profiling use cases ,1 ≤ N ≤ 100,N The total weight of each weight does not exceed 100000.
Output format
Output an integer to represent the answer .
sample input
3
1 4 6
sample output
10
analysis
The violent search of this problem will definitely timeout ,dfs In general , Yes 50% The point of .
The positive solution of this problem is dp( Why can't vegetable chicken dp), Then let's analyze dp How to do it :
- State means f[i][j]: Before presentation i Choose one of the weights , The weight weighed is j The state of , by 1 It means you can weigh , by 0 Cannot weigh out .
- State shift :
- a[i] == j, that f[i][j] It must be called
- a[i] != j, Then you can go from f[i - 1][j],f[i - 1][abs(j - a[i])]( Essential for f[i - 1][j - a[i]], To prevent negative subscripts , So take the absolute value ),f[i - 1][j + a[i]] this 3 In this case, transfer .
f[i - 1][j]:i - 1 A weight can weigh ,i One can also weigh out
f[i - 1][j - a[i]]: Add the current weight
f[i - 1][j + a[i]]: Subtract the current weight
Satisfy 3 Any one of these , You can judge f[i][j] Weight of j Can it be called
Reference code 1(dfs)---- too 50% Example (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;
}
Reference code 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;
}
边栏推荐
- Basic use of redis
- Vs2019 use wizard to generate an MFC Application
- Vs2019 first MFC Application
- ES6 promise object
- [download app for free]ineukernel OCR image data recognition and acquisition principle and product application
- 项目实战-后台员工信息管理(增删改查登录与退出)
- Codeforces Round #753 (Div. 3)
- Rhcsa certification exam exercise (configured on the first host)
- Are you monitored by the company for sending resumes and logging in to job search websites? Deeply convinced that the product of "behavior awareness system ba" has not been retrieved on the official w
- Codeforces Round #771 (Div. 2)
猜你喜欢
Vs2019 desktop app quick start
QT creator test
Leetcode 461 Hamming distance
Software testing and quality learning notes 3 -- white box testing
Request object and response object analysis
Mtcnn face detection
Pytorch基础
Django running error: error loading mysqldb module solution
Learning question 1:127.0.0.1 refused our visit
Face recognition_ recognition
随机推荐
Learn winpwn (3) -- sEH from scratch
ES6 let and const commands
jS数组+数组方法重构
01项目需求分析 (点餐系统)
What does usart1 mean
记一次某公司面试题:合并有序数组
Nanny level problem setting tutorial
Armv8-a programming guide MMU (2)
JDBC原理
Vs2019 first MFC Application
L2-004 这是二叉搜索树吗? (25 分)
Machine learning notes week02 convolutional neural network
What does BSP mean
Windows下安装MongDB教程、Redis教程
error C4996: ‘strcpy‘: This function or variable may be unsafe. Consider using strcpy_s instead
Face recognition_ recognition
AcWing 179. Factorial decomposition problem solution
JDBC原理
误删Path变量解决
QT creator create button