The Preliminary Contest for ICPC Asia Shanghai 2019 J. Stone game —— 退背包

CSL loves stone games. He has nn stones; each has a weight a_iai. CSL wants to get some stones. The rule is that the pile he gets should have a higher or equal total weight than the rest; however if he removes any stone in the pile he gets, the total weight of the pile he gets will be no higher than the rest. It's so easy for CSL, because CSL is a talented stone-gamer, who can win almost every stone game! So he wants to know the number of possible plans. The answer may be large, so you should tell CSL the answer modulo 10^9 + 7109+7.

Formerly, you are given a labelled multiset S=\{a_1,a_2,\ldots,a_n\}S={a1,a2,…,an}, find the number of subsets of SS: S'=\{a_{i_1}, a_{i_2}, \ldots, a_{i_k} \}S′={ai1,ai2,…,aik}, such that

\left(Sum(S') \ge Sum(S-S') \right) \land \left(\forall t \in S', Sum(S') - t \le Sum(S-S') \right) .(Sum(S′)≥Sum(S−S′))∧(∀t∈S′,Sum(S′)−t≤Sum(S−S′)).

InputFile

The first line an integer TT (1 \leq T \leq 10)1≤T≤10), which is the number of cases.

For each test case, the first line is an integer nn (1 \leq n \leq 3001≤n≤300), which means the number of stones. The second line are nn space-separated integers a_1,a_2,\ldots,a_na1,a2,…,an (1 \leq a_i \leq 5001≤ai≤500).

OutputFile

For each case, a line of only one integer tt --- the number of possible plans. If the answer is too large, please output the answer modulo 10^9 + 7109+7.

样例输入复制

2
3
1 2 2
3
1 2 4

样例输出复制

2
1

样例解释

In example 1, CSL can choose the stone 1 and 2 or stone 1 and 3. 

 In example 2, CSL can choose the stone 3.

题意：
给你n个只有重量的石头，让你取出一些石头，记这个重量为s1（其中最轻的石头的重量为t），剩下石头的重量为s2，问你有多少种情况使得s1>=s2&&s1-t<=s2.

题解：
背包计数问题做的少，这个退背包的思想倒是第一次见。

思路来自：​​ 从小到大枚举石头的重量，然后先退掉每一个重量，然后再for一遍可行的区间：
max((s+1)/2−a[i],0) 因为我们退掉了a[i]的重量，所以左端点就是这个值，然后右端点，由与我们枚举的是j，但是我们已经减掉了a[i]，所以它其实是a[i]+j，不等式是这样的：(j+a[i])−a[i]<=s−(j+a[i])
for一遍即可。

正规题解：直接看代码二，一看就懂

#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
typedef long long ll;
const ll MOD=1e9+7;
ll n,sum;
ll a[400],dp[maxn];  //dp[i]-前n个数组成和为i的方案数
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        
        sum=0;
        scanf("%lld",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&a[i]);
            sum+=a[i];
        }
        sort(a+1,a+n+1);
        memset(dp,0,sizeof(dp));
     
        dp[0]=1;
        for(int i=1; i<=n; i++)
        {
            for(ll j=sum; j>=a[i]; j--)
            {
                dp[j]=(dp[j-a[i]]+dp[j])%MOD;
            }
        }
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=a[i];j<=sum;j++)
                dp[j]=(dp[j]-dp[j-a[i]]+MOD)%MOD;
            for(int j=max((sum+1)/2-a[i],0LL);j<=sum-j-a[i];j++)
                ans=(ans+dp[j])%MOD;
        }
        printf("%lld\n",ans);
        
        
      
    }


    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls rt << 1
#define rs rt << 1|1
#define mid ((l + r) >> 1)
#define lson l, mid, ls
#define rson mid + 1, r, rs
const int maxn = 305;
const int mod = 1e9 + 7;
int a[maxn];
ll dp[150010];
 
 
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        memset(dp, 0, sizeof(dp));
        int n;
        ll sum = 0;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        sort(a + 1, a + n + 1, greater<int>());
        dp[0] = 1;
        ll ans = 0;
        for(int i = 1; i <= n; ++i)
        {
            for(int 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;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

学长正规思想

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define dep(i,a,b) for(register int i=(a);i>=(b);i--)

using namespace std;
const int maxn=200010;
const ll mo=1e9+7;
int n,m,k,b;
ll sum[maxn];
int a[maxn];
ll ans;
ll dp[maxn];
int main()
{
    int T,cas=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int mm=0;
        ans=0;
        rep(i,1,n)
        {
            scanf("%d",&a[i]);
            mm+=a[i];
        }
        sort(a+1,a+1+n);
        int m=mm;
        rep(i,0,m) sum[i]=0;
        sum[0]=1;
        dep(i,n,1)
        {
            rep(j,0,a[i]-1) dp[j]=0;
            dep(j,m,a[i])
            dp[j]=sum[j-a[i]];
            rep(j,0,m)
            if(dp[j])
            {
                if(j>=a[i]&&(m<=2*j)&&(2*j-a[i]<=m))
                {
                    ans=(ans+dp[j])%mo;
                    //cout<<i<<" * "<<j<<endl;
                }
                sum[j]=(sum[j]+dp[j])%mo;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}