38 lines
1.1 KiB
C++
38 lines
1.1 KiB
C++
// lanqiao 1447 砝码称重(DP)
|
||
#include<bits/stdc++.h>
|
||
using namespace std;
|
||
/* 类似于背包DP
|
||
状态:dp[i][j]对于前i个砝码，能否称出重量为j的情况
|
||
状态转移方程:
|
||
dp[i][j]=dp[1-1][j]+dp[i-1][j+w[i]]+dp[i-1][abs(j-w[i])]
|
||
这个公式包含了三种情况:
|
||
1.不使用第i个砝码，此时可称重的方案数就是dp[i-1][j]
|
||
2.使用了第i个砝码，并将其放在天平的一边，此时额外增加的可称重方案数dp[i-1][j+w[i]]
|
||
3.使用了第i个砝码，并将其放在天平的另一边，此时额外增加的可称重方案数dp[i-1][abs(j-w[i])]
|
||
*/
|
||
const int N = 1e2 + 10, M = 1e5 + 10;
|
||
int w[N], dp[N][M];
|
||
int main(){
|
||
int n, sum = 0;
|
||
cin >> n;
|
||
for(int i = 1; i <= n; i++){
|
||
cin >> w[i];
|
||
sum += w[i];
|
||
}
|
||
dp[0][0] = 1;
|
||
for(int i = 1; i <= n; i++){
|
||
for(int j = 0; j <= sum; j++){
|
||
dp[i][j] = dp[i-1][j] + dp[i-1][j+w[i]] + dp[i-1][abs(j-w[i])];
|
||
}
|
||
}
|
||
int cnt = 0;
|
||
for(int i = 1; i <= sum; i++){
|
||
if(dp[n][i]) cnt++;
|
||
}
|
||
cout << cnt << endl;
|
||
return 0;
|
||
}
|
||
/* test samples -> 10
|
||
3
|
||
1 4 6
|
||
*/ |