思路:动态规划的选择问题
思路:有点像01背包,但是又不像,因为这里的状态分为三个,并不是两个,也就是说,这是一个很好的01背包变形问题。
状态有三个,也就是放到左边,放到右边,或者说不选择它。
状态分析之后,我们分析一下,这里并不是对于物品的最大价值进行求解,也不是对于物品的方案数进行存储,而是对于可行与不可行的分析。
所以,我们只需要判断其他状态能不能推出这个状态就行了,那么我们开一个二维数组方便于理解。这里的f也就是对于前i个数字,能否达到j的状态定义。
三个状态可以这样写:f[i][j]=f[i-1][j]不选;f[i][j]=f[i][abs(j-arr[i])]砝码放置于异侧;f[i][j]=f[i][j+arr[i]]砝码放在一块。
只要其中有一个满足,这个状态就可以达成,也就是并行条件。
上代码:
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<set>
#define int long long
#define MAX 101
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
using PII=pair<int, int>;
int n, m;
int counts;
int arr[MAX];
int f[MAX][200005];
signed main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
int sum = 0;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
sum += arr[i];
}
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= sum; j++) {
f[i][j] = f[i - 1][j] || f[i - 1][j + arr[i]] || f[i - 1][abs(j - arr[i])];
}
}
for (int i = 1; i <= sum; i++) {
if (f[n][i])
counts++;
}
cout << counts << endl;
return 0;
}