砝码称重

dp

题目描述

你有一架天平和 N 个砝码，这 N 个砝码重量依次是$W_1,W_2,W_3,⋅⋅⋅,W_N$ 。
请你计算一共可以称出多少种不同的正整数重量？
注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 N 。
第二行包含 N 个整数：$W_1,W_2,W_3,⋅⋅⋅,W_N$ 。

输出格式

输出一个整数代表答案。

数据范围

对于$50\%$的评测用例，$1≤N≤15$。
对于所有评测用例，$1≤N≤100$，N 个砝码总重不超过$10^5$。

输入样例：

3
1 4 6

输出样例：

10

样例解释

能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11 。

1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
9 = 4 + 6 − 1；
10 = 4 + 6；
11 = 1 + 4 + 6。

题解

(DP) $O(nm)$

y总用了在状态转移方程上用了dp(i) |= dp(i-1)如果i-1个的时候不合法，则i也会不合法，同理i-1合法，或运算会使得dp(i)的结果与i-1相同

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false), cin.tie(0)
#define sd(n) scanf("%d" , &n)
#define rep(i, a, n) for ( int i = a; i <= n; i++)
#define per(i, a, n) for ( int i = n; i >= a; i--)
#define debug(x) cout << #x << ": " << x << endl
#define MOD 1000000007
#define INF 0x3f3f3f3f
typedef long long LL;
using namespace std;
const int N =2e5 + 10 , B = 1e5 ;
int n , m , w[150];
int dp[150][N];
int main()
{
    sd(n);
    rep(i , 1 , n)
    {
        sd(w[i]);
        m += w[i];
    }
    /** Base偏移量
     *  对于前i个砝码，总重量为j的方法集合 
     *  属性 ： 可以称出该种重量重（Bool类型） 0 / 1
     * 1、不选j砝码 dp[i][j] = dp[i-1][j];
     * 2、j放左边   dp[j][j] += dp[i-1][j - w[i]];
     * 3、j放右边   dp[i][j] += dp[i-1][j + w[i]];
     **/
    dp[0][B] = 1;
    rep(i , 1 , n)
        rep(j , -m , m)
        {
            dp[i][j + B] = dp[i-1][j + B];
            if(j - w[i] >= -m) dp[i][j + B] += dp[i-1][j - w[i] + B];
            if(j + w[i] <=  m) dp[i][j + B] += dp[i-1][j + w[i] + B];
        }
    int ans = 0;
    rep(i , 1 , m)
        if(dp[n][i + B]) ans ++;
    cout << ans;
    return 0;
}

(位运算) $O(n)$

不懂bitset可以戳这里

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false), cin.tie(0)
#define sd(n) scanf("%d",&n)
#define rep(i, a, n) for (register int i = a; i <= n; i++)
#define per(i, a, n) for (register int i = n; i >= a; i--)
#define debug(x) cout << #x << ": " << x << endl
#define MOD 1000000007
#define INF 0x3f3f3f3f
typedef long long LL;
using namespace std;
const int N =1e5 + 10 ;
int n , w[150];
bitset<N> s;
int main()
{
    sd(n);
    rep(i , 1 , n) sd(w[i]);
    s[0] = 1;   //边界
    rep(i , 1 , n)  s |= s << w[i];
    rep(i , 1 , n)  s |= s >> w[i];
    cout << s.count() -1;   //有多少个1，除去重量位0的边界
    cout << endl;
    return 0;
}

运行时间对比图如下：