第十二届蓝桥杯c++B组第一场第七题

方法一：dfs(可过5/10个数据)

#include<iostream>

using namespace std;

const int N = 100010;

int n,sum,res;
int a[N],w[N];

void dfs(int u,int ans)
{
    if(u > n)
    {
        if(ans <= 0) return ;
        else
        {
            a[ans]++;
            return ;
        }
    }
    dfs(u+1,ans);
    dfs(u+1,ans + w[u]);
    dfs(u+1,ans - w[u]);
}

int main()
{
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>w[i],sum += w[i];
    dfs(1,0);
    for(int i = 1;i<=sum;i++)
    {
        if(a[i] > 0) res++;
    }
    cout<<res;
    return 0;
}

方法二：dp

#include<iostream>

using namespace std;

const int N = 110,M = 200010,B = M / 2;

int n,m;
int w[N];
bool f[N][M];

int main()
{
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>w[i],m += w[i];
    f[0][B] = true;

    for(int i = 1;i<=n;i++)
     for(int j = -m;j<=m;j++)
      {
          f[i][j + B] = f[i-1][j + B];
          if(j - w[i] >= -m) f[i][j + B] |= f[i-1][j - w[i] + B];
          if(j + w[i] <= m) f[i][j + B] |= f[i-1][j + w[i] + B];
      }

      int res = 0;
      for(int j = 1;j<=m;j++)
      {
          if(f[n][j+B]) res++;
      }
      cout<<res;
      return 0;
}