题目

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 $W_1$ , $W_2$ ,⋅⋅⋅, $W_N$ 。

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

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

输入格式

输入的第一行包含一个整数 N。

第二行包含 N 个整数： $W_1$ , $W_2$ ,⋅⋅⋅, $W_N$ 。

输出格式

输出一个整数代表答案。

数据范围

对于 50% 的评测用例，1≤N≤15。
对于所有评测用例，1≤N≤100，N 个砝码总重不超过 $10^5$ 。

输入样例：

3
1 4 6

输出样例：

样例解释

能称出的 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。

想法

想法很朴素。这么多东西，一下子放进来算，肯定算不明白，那只能一个一个来。

一个一个来，那怎么表示第 i 个进来之前的之前的结果？

噢吼~

这不是动态规划的思想嘛。

那就设计下动态规划的表示。目测这个dp[][]应该具有三要素：

到第几个了
到这里的方案数
到这里之前有的方案是哪些

瞄一眼总重不超过 $10^5$ ，大胆设 dp[i][j] 表示加入第 i 个砝码时，重量 j 是不是被用了。（emmmm？好像又不是动态规划了……）

状态转移方程：dp[i][j]=max(max(dp[i-1][j], dp[i-1][j-a[i]]), dp[i-1][j+a[i]])
其中 a[i] 表示第 i 个砝码的重量

结果：sum(dp[n]) 对最后一个砝码放入后的结果求和。

注意点：

重量可能为负数（例如 9 可能是这么算出来的：(3-4)+10），所以要加 offset 表示负数。
空间问题，加加减减的可能导致数组越界了，记得加个判断。
空间问题，怕数组开大了，采用滚动dp，不储存之前的结果。

代码

#include<bits/stdc++.h>
using namespace std;
int N;
// 负数 
const int offset = 100052;
// 总数
const int maxn = offset+100052;
// 砝码
int a[1005];
// 滚动dp
int dp[2][maxn];// sort 用的（实际上没什么用，复习一下罢了）
bool cmp(int a,int b){return a>=b;
}int main(){cin>>N;// 初始化为0memset(dp,0,sizeof(dp));int n = 1;while(cin>>a[n]){n++;}// 排序（没什么用其实，可以不要）sort(a+1,a+n,cmp);// 对 0 置 1dp[0][offset]=1;for(int i=1;i<n;i++){for(int j=0;j<maxn;j++){// 判断一下，怕 段错误if(j+a[i]<maxn && j-a[i]>0)dp[1][j] = max(max(dp[1-1][j], dp[1-1][j-a[i]]),dp[1-1][j+a[i]]);}// dp滚动一下for(int j=0;j<maxn;j++){dp[0][j] = dp[1][j];}
//		可以输出看看
// 		for(int j=offset+1;j<maxn;j++)
// 		    if (dp[0][j]>0)
// 		        cout<<j-offset<<"\n";
// 		cout<<"\n\n";}// 统计结果int count = 0;for(int i=offset+1;i<maxn;i++){if(dp[0][i]>0){count++;
// 			cout<<dp[n-1][i]<<"\n";}}cout<<count;return 0;
}