AcWing 3417. 砝码称重(记忆化搜索)
原题链接
中等
作者:
无名小卒x
,
2022-12-13 16:04:46
,
所有人可见
,
阅读 187
#include<bits/stdc++.h>
using namespace std;
const int N =1e5;
int mp[107][200010];
int a[N], n;
int dfs(int u, int s)
{
if(mp[u][s] != -1) return 0;
if(u == n) return mp[u][s] = s > N ? 1 : 0;
int &v = mp[u][s]; v = 0;
v += dfs(u + 1, s - a[u]);
v += dfs(u + 1, s + a[u]);
v += dfs(u + 1, s);
return v;
}
int main()
{
cin >> n;
memset(mp,-1,sizeof mp);
for(int i = 0; i <= n; i++ ){
scanf("%d", &a[i]);
}
cout << dfs(0,N) << endl;
return 0;
}