运维开发网
广告位招商联系QQ:123077622
 
广告位招商联系QQ:123077622

【2019上海网络赛】

运维开发网 https://www.qedev.com 2020-07-21 11:40 出处:网络 作者:运维开发网整理
B题:分成两序列,A>B,A-(a[i]属于A里面的)<=B; #include<bits/stdc++.h>using namespace std;#define ll long longconst ll mod=1e9+7;const ll inf=1e18;ll dp[300*500+5];int a[300];int main(){ int t; scanf("%d",&t); while

B题:分成两序列,A>B,A-(a[i]属于A里面的)<=B;

#include<bits/stdc++.h>using namespace std;#define ll long longconst ll mod=1e9+7;const ll inf=1e18;ll dp[300*500+5];int a[300];int main(){ int t; scanf("%d",&t); while(t--) { int n,s=0; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]),s+=a[i]; sort(a+1,a+1+n); for(int i=1;i<=s;i++)dp[i]=0; dp[0]=1; for(int i=1;i<=n;i++) for(int j=s;j>=a[i];j--) (dp[j]+=dp[j-a[i]])%=mod; ll ans=0; for(int i=1;i<=n;i++) { for(int j=a[i];j<=s;j++)///表示去a[i]后的方案数 dp[j]=(dp[j]-dp[j-a[i]]+mod)%mod; for(int j=max((s+1)/2-a[i],0);j<=s-j-a[i];j++)///因为我们减掉的a【i】得是任意的,那肯定是最小的也得满足,所以我们上面先排序了后一个一个枚举 ans=(ans+dp[j])%mod; } printf("%lld\n",ans); } return 0;}

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消