博客

题目地址：

https://www.dotcpp.com/oj/problem1449.html。刚看到这个题目第一个想法就是深搜

#include <iostream>
using namespace std;
long long n, s, a, b;
long long sum;
long long cnt = 0;
long long mo = 100000007;
int dfs(long long nn, long long rn) {
// cout << "dfs ?" << nn << ", " << rn << endl;
	sum += nn;
	if(rn == 0) {//能用的减数或加数用完了?
//cout << "sum ? " << sum << endl;
		if(sum == s) {
			sum -= nn;//减去恢复 以便再次遍历 ，测试 5 10 2 3 就发现有差异 （有的情况前面相同而后面不同）?
// cout << "cnt" << endl;;
			cnt++;//种数?
			cnt %= mo;
			return 1;
		} else {
			sum -= nn;//减去恢复 以便再次遍历 ，
			return 0;
		}
	}
	dfs(nn + a, rn - 1);
	dfs(nn - b, rn - 1);
	sum -= nn;//减去恢复 以便再次遍历 ，
}
int main(void) {
	cin >> n >> s >> a >> b;
//dfs(2, 3);
	for(long long i = s - n * a; i < s + n * b; i++) {
		sum = 0;
		dfs(i, n - 1);//从第一个数的最值[s-n*a,s+n*b]之间测试怎样加减达到给定的和值 ，所以后面的数是n-1?
	}
	cout << cnt << endl;
	return 0;
}

这个题目的最优解是用到01背包问题，滚动数组，下面看两位大佬的博客：

https://blog.csdn.net/wr132/article/details/43861145，


https://blog.csdn.net/more_ugly_less_bug/article/details/54957478