技术教程 编程教程 计蒜客（Stone Game）01背包 正文

计蒜客（Stone Game）01背包

2023-03-09,,

题意：在集合中挑一些数，形成一个集合S，剩下的数形成另一个集合P，使得S>= P ，并且对于S中任意元素ai，S-ai<=P

问有多少种方案。

题目链接：https://nanti.jisuanke.com/t/41420

只要减S堆中最小的石头后满足条件，那么该取法就满足题意

设dp【k】为S堆总重量为k的方案数

把ai从大到小排序；遍历时ai就变成了最小的那块石头

所以就是01背包，取或不取这个石头；最后把满足题目条件的加到ans中

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int mod=1e9+7;

ll dp[150005];

int a[305];

int main()

{

    int i,j,n,t;

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        ll sum=0;

        for(i=1;i<=n;i++){

            scanf("%d",&a[i]);

            sum+=a[i];

        }

        sort(a+1,a+1+n,greater<int>());

        memset(dp,0,sizeof dp);

        dp[0]=1;

        ll ans=0;

        for(i=1;i<=n;i++){

            for(j=sum;j>=a[i];j--){

                dp[j]=(dp[j]+dp[j-a[i]])%mod;

                if(j>=sum-j&&j-a[i]<=sum-j)ans=(ans+dp[j-a[i]])%mod;

                //满足条件就把选了a【i】的方案数dp[j-a[i]]加上 而dp【j】则包含了没选a【i】的方案数，没选的前面已经加过了

            }

        }

        printf("%lld\n",ans);

    }

    return 0;

}

计蒜客（Stone Game）01背包的相关教程结束。

《计蒜客（Stone Game）01背包.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!