The Preliminary Contest for ICPC Asia Shanghai 2019 J. Stone game

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

思路:01背包方案 

           当a(a∈S′)为最小值            

           如果Sum(S′)−a≤Sum(S−S′)成立

           那么(∀t∈S′,Sum(S′)−t≤Sum(S−S′))恒成立 

           从大到小排序即当前a[i]为已选石头中的最小值

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int a[400];
int dp[150001];
int cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int T;
    scanf("%d",&T);
    int n;
    while(T--)
    {
        scanf("%d",&n);
        int s=0,ans=0; 
        for(int i=0;i<n;i++) scanf("%d",&a[i]),s+=a[i];
        sort(a,a+n,cmp);
    memset(dp,0,sizeof dp);
    dp[0]=1;
    for(int i=0;i<n;i++) 
        for(int j=s;j>=a[i];j--)
        {
            if(j>=s-j&&j-a[i]<=s-j) ans=(ans+dp[j-a[i]])%mod;
            dp[j]=(dp[j]+dp[j-a[i]])%mod;
        }
    printf("%d\n",ans);
    }
    return 0;
}
上一篇:Docker容器同步主机时间


下一篇:Centos7 修改时间为中国时区