今天是动归练习题第2题。
给你n个整数，每个数可选或不选，要求选一些数，使它们的和为S，问有多少种方案？
输入格式
第一行：2个整数n和s，范围都在[1, 100]。
第二行：n个整数，每个数范围在[-100, 100]。
输出格式
输出方案数。（答案不超过2^63）
输入/输出例子
输入：
6 10
3 4 7 8 -1 2
输出：
4
样例解释：
3+7, 3+8-1, 4+7-1, 8+2
解体思路：
这题其实属于模版题，搞清楚状态数组 f 代表什么即可，f [ i ] 代表的就是和为 i 的方案数。另一个难点就是有负数，而数组下标不能为负数，所以数组的下标要加10000。
参考代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,s,a[1000005],f[1000005];
signed main(){cin>>n>>s;for(int i=1;i<=n;i++){cin>>a[i];}f[10000]=1;for(int i=1;i<=n;i++){if(a[i]>=0){for(int j=20000;j>=a[i];j--){f[j]=f[j]+f[j-a[i]];}}if(a[i]<0){for(int j=0;j<=20000;j++){f[j]=f[j]+f[j-a[i]];}}}cout<<f[10000+s];return 0;
}今天就讲到这，拜拜！