题目: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; }