2023.11.25学习笔记-526互联

集合 Subset Sums

P1466 [USACO2.2] 集合 Subset Sums - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

背包板子题，有一说一看出来很简单贴ac code

#include<iostream>
using namespace std;

long long  a[50];

int main()
{
    int n;   cin>>n;
    int sum=0,ans=0;
    for(int i=1;i<=n;i++)sum+=i;
    if(sum%2==0)sum>>=1;
    else{
        cout<<0;
        exit(0);
    }
    a[0]=1;
    for(int i=n;i>0;i--)
    {
        for(int j=sum;j>=0;j--)
        {
            if(a[j])a[j+i]+=a[j];
        }
    }
    cout<<a[sum]/2;
    system("pause");
    return 0;
}

一般dp解决没有问题，但是也可以用dfs解，虽然我一开始就想到了dfs，但是由于我是蒟蒻所以没有写出来，下面贴佬的dfs：

#include<cstdio>
typedef long long LL;
const int M=1e3+5;
LL b[M];
int n;
LL ans;
int main(){
    scanf("%d",&n);
    if(((1+n)*n/2)&1)puts("0");
    else{
        for(int i=0;i<(1<<(n/2));++i){
            int cur=0;
            for(int j=0;(i>>j)>0;++j)if((i>>j)&1)cur+=(j+1);
            b[cur]++;
        }
        for(int i=0;i<(1<<(n-n/2));++i){
            int cur=0;
            for(int j=0;(i>>j)>0;++j)if((i>>j)&1)cur+=j+n/2+1;
            if((1+n)*n/4>=cur)
            ans+=b[(1+n)*n/4-cur];
        }
        printf("%lld\n",ans/2);
    }
    return 0;
}

。。。。。。。。