题目描述
你有一架天平和 NN 个砝码, 这 NN 个砝码重量依次是 W_{1}, W_{2} ,⋯,W_{N}。 请你计算一共可以称出多少种不同的重量?
注意砝码可以放在天平两边。
输入格式：
输入的第一行包含一个整数 N。
输入的第一行包含一个整数 N。
第二行包含 N 个整数: W_{1}, W_{2}, W_{3}。。。
输出格式：
输出一个整数，表示答案。
输出一个整数，表示答案。
题解
不会写递推，用了一个笨蛋朴素一点的方法，记 dp[i][j]为前 i 个数是否可以表达数字 j，若可以则为 1，不可以则为 0。此时可以知道，若 dp[i-1][j]为 1 则 dp[i][j]也为一，同时可以推出左右各放一次得到的重量也为 1，即 dp[i][j + a[i]]和 dp[i][abs(j – a[i])]也为 1.最后遍历最后一行加和即可。
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mem(vis, num) memset(vis, num, sizeof(vis));
using namespace std;
int dp[110][100010], a[110];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
mem(dp, 0);
int n, ans = 0;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= n; i++){
dp[i][a[i]] = 1;
for(int j = 1; j <= 100000; j++){
if(dp[i - 1][j] != 0){
dp[i][j] = 1;
dp[i][j + a[i]] = 1;
dp[i][abs(j - a[i])] = 1;
}
}
}
for(int i = 1; i <= 100000; i++){
ans += dp[n][i];
}
cout << ans << endl;
return 0;
}
