Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic describes

12. You have a balance and N weights, W1,W2, WN.

Please calculate how many different positive integer weights you can weigh?

Note that weights 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 integers: W1,W2,W3,⋅… Wn\

Output format: Output an integer to represent the answer. \

Data range

For 50% of the test cases, 1≤N≤15. For all test cases, 1≤N≤100, N weights total weight not exceeding 1E5.

Train of thought

It’s a cliche. Find a pattern. If we’re going to use dynamic programming, we need an idea of state transitions.

It’s not hard to see that each time we add a new weight, assuming we already have some weights in between and we know all the weights that can be weighed, we add and subtract this weight for each of the weights that we can weigh before. If a new weight is obtained, record it. After enumerating, you get all the new weights that can be weighed. And so on, dp.

Since the known weight of all weights is not more than 1E5, which is a small number, we can enumerate the weight of weights in DP.

Let dp(I,j), whose value represents whether the previous I weights can weigh j, 1 if they can, 0 if they can’t. Range: 1<= I <=n,1<=j<=1e5. Note here that j cannot be considered as 0, because 0 is not a weight. Or you don’t have to weigh the 0.

So, for i0, we simply enumerate all js where dp(i0-1,j) is 1, and then set dp(i0,j+w),dp(i0,j),dp(i0,abs(j-w)) to all be 1. Notice that you take the absolute value of subtraction. In order to save space, we compress the dimension of I and change it into two dp[1e5] one-dimensional arrays in the code. Each time we enumerate one of them as the state of I0-1 and the other as the state of i0. See the code for details.

code

#include<bits/stdc++.h> using namespace std; const int maxn=100000+5; int dp1[maxn]; int dp2[maxn]; int arr[105]; int main(){ int n; cin>>n; for(int i=0; i<n; i++){ cin>>arr[i]; } dp1[arr[0]]=1; int *dp=dp2; int *last=dp1; for(int i=1; i<n; i++){ memcpy(dp,last,sizeof(int)*maxn); dp[arr[i]]=1; for(int j=1; j<maxn; j++){ if(last[j]){ dp[j+arr[i]]=1; dp[abs(j-arr[i])]=1; } } if(last==dp1){ last=dp2; dp=dp1; }else{ last=dp1; dp=dp2; } } int cnt=0; for(int i=1; i<maxn; i++){ if(last[i])cnt++; } cout<<cnt; return 0; }Copy the code