2019-ICPC-Shanghai-online-J

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

题目大意

给你一些石头,让你选一些石头重量大于剩余的重量,且去掉任意一个你选的石头之后总重量小于等于剩余重量

思路

将石头按从大到小排序,然后遍历选取，以当前的石头为最小值,也就是当前的石头一定要选,比它大的可选可不选,比它小的一定不选
然后就是背包问题了,dp[j]代表选择石头的总重量为j的方案数,判断一下j合不合法,合法就加上dp[j-num[i]];

AC代码

#include <iostream>
#include <cstring> 
#include <algorithm> 
#include <cstdio>
using namespace std;
typedef long long ll;
#define wfor(i,j,k) for(i=j;i<k;++i)
#define mfor(i,j,k) for(i=j;i>=k;--i)
// void read(int &x) {
// 	char ch = getchar(); x = 0;
// 	for (; ch < '0' || ch > '9'; ch = getchar());
// 	for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
// }
const int maxn=305;
ll dp[150005];
int num[maxn];
const int mod=1e9+7;
int main()
{
    std::ios::sync_with_stdio(false);
    #ifdef test
    freopen("F:\\Desktop\\question\\in.txt","r",stdin);
    #endif
    #ifdef ubuntu
    freopen("/home/time/debug/debug/in","r",stdin);
    freopen("/home/time/debug/debug/out","w",stdout);
    #endif
    int t;
    cin>>t;
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        int n;
        cin>>n;
        int i;
        int sum=0;
        wfor(i,1,n+1)
        {
            cin>>num[i];
            sum+=num[i];
        }
        sort(num+1,num+n+1);
        int j;
        ll ans=0;
        dp[0]=1;
        mfor(i,n,1)
        {
            mfor(j,sum,num[i])
            {
                int rest=sum-j;
                if(j>=rest&&j-num[i]<=rest)
                {
                    ans+=dp[j-num[i]];
                    ans%=mod;
                }
                dp[j]+=dp[j-num[i]];
                dp[j]%=mod;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}