题目描述

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN。

请你计算一共可以称出多少种不同的正整数重量？

注意砝码可以放在天平两边。

输入样例：

3
1 4 6

输出样例：

10

算法

(dp思路) $O(n*m)$

考虑第i个物品时，考虑之前的状态，对于每个之前已经存在的状态j:
1.（j重量小于w[i]) dp[w[i]-j]=1,dp[w[i]+j]=1;
2.(j重量大于w[i])  dp[w[i]+j]=1,dp[j-w[i]]=1;
(这里得用滚动数组存临时更新)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=100100;
bool dp[N],temp[N];
int a[N],n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    int sum=0;
    for(int i=1;i<=n;i++)sum+=a[i];
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=sum;j++)
        {
            if(dp[j]){
                if(j<=a[i])temp[a[i]-j]=1;
                if(j>=a[i])temp[j-a[i]]=1;
                temp[j+a[i]]=1;
            }
        }
        for(int j=0;j<=sum;j++)dp[j]|=temp[j];
    }
    int res=0;
    for(int i=1;i<=sum;i++)if(dp[i])res++;
    cout<<res<<endl;
    return 0;
}