問題描述
你有一架天平和?N?個砝碼，這?N?個砝碼重量依次是?W1,W2,???,WN?。
請你計算一共可以稱出多少種不同的重量？ 注意砝碼可以放在天平兩邊。
輸入格式
輸入的第一行包含一個整數?N。
第二行包含?N?個整數：W1,W2,W3,???,WN?。
輸出格式
輸出一個整數代表答案。
樣例輸入
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。
評測用例規模與約定
對于?50的評測用例，1≤N≤15。
對于所有評測用例，1≤N≤100,N1≤N≤100,N?個砝碼總重不超過?100000。
?
?
#include<iostream>
#include<cmath>
using namespace std;const int N = 110;
const int M = 2e5+10; //j的范圍是 [-m, m]，M為最大可能重量的兩倍
int n;
int m; //總重量
int w[N];
bool f[N][M]; //f[i][j]：前i個砝碼能否稱出重量j
int ans;int main()
{cin>>n;for(int i=1; i<=n; ++i){cin>>w[i];m += w[i];}f[0][0]=1; //初始化：0個砝碼稱出0//枚舉前i個砝碼for(int i=1; i<=n; ++i){//枚舉所有可能的重量for(int j=0; j<=m; ++j){//不選當前砝碼 || 選砝碼放到左盤 || 選砝碼放到右盤f[i][j]=f[i-1][j] || f[i-1][abs(j-w[i])] || f[i-1][j+w[i]];}}for(int i=1; i<=m; ++i){if(f[n][i]) ans++;}cout<<ans;return 0;
}
