[Bluebridge cup 2021 preliminary] weight weighing

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 ：

1. 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 .
2. State shift ：
   1. a[i] == j, that f[i][j] It must be called
   2. 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; 
}