关注
#include <bits/stdc++.h>
#include <thread>
#define input freopen("input.txt", "r", stdin)
#define output freopen("output.txt", "w", stdout)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define random(x) (rand()%x)+1
using namespace std;
const int maxn=1e5+5;
using LL =long long;
const int inf = 0x3f3f3f3f;
const int mod=1e6+3;
int dp[51][maxn/2];
int main(int argc, char const *argv[])
{
input;output;
int T,n,arr[101],sum;
scanf("%d",&T);
while(T--){
sum=0;
scanf("%d",&n);
assert(n<=100);
for(int i=0;i<n;i++){
scanf("%d",arr+i);
sum+=arr[i];
}
assert(sum<maxn);
for(int i=0;i<=(n+1)/2;i++)
for(int j=0;j<=sum/2;j++)
dp[i][j]=-inf;
dp[0][0]=0;
for(int i=0;i<n;i++)
for(int j=(n+1)/2;j>0;j--)
for(int k=sum/2;k>=arr[i];k--)
dp[j][k]=max(dp[j][k],dp[j-1][k-arr[i]]+arr[i]);
int ans=0;
for(int i=0;i<=sum/2;i++)
ans=max(ans,max(dp[n/2][i],dp[(n+1)/2][i]));
printf("%d %d\n",ans,sum-ans);
}
return 0;
} 第三题是背包,问题等价于求n/2或者(n+1)/2个人放入总战斗力和1/2的背包中,看最多能放入多少战斗力,话说求第二题的思路
查看原帖
点赞 3
相关推荐
牛客热帖
更多
正在热议
更多
# 第一份工作应该选高薪还是热爱? #
66303次浏览 591人参与
# 不考虑薪资和职业,你最想做什么工作呢? #
91815次浏览 677人参与
# 秋招签约后的心态变化 #
82352次浏览 812人参与
# 听劝,这个公司值得去吗 #
485851次浏览 1700人参与
# 你觉得早上几点上班合适? #
72148次浏览 303人参与
# 学历贬值真的很严重吗? #
24311次浏览 172人参与
# 机械人与华为的爱恨情仇 #
120088次浏览 957人参与
# 一人推荐一个值得去的通信/硬件公司 #
186394次浏览 1859人参与
# 打工人的工作餐日常 #
52962次浏览 415人参与
# 哪些公司真双非友好? #
15720次浏览 82人参与
# 26届的你们有几段实习? #
43265次浏览 484人参与
# 月薪多少能在一线城市生存 #
26918次浏览 300人参与
# 双非能在秋招上岸吗? #
221556次浏览 1172人参与
# 你以为的实习VS真实的实习 #
28884次浏览 263人参与
# 你后悔自己读研吗? #
20110次浏览 239人参与
# 当下环境,你会继续卷互联网,还是看其他行业机会 #
117795次浏览 812人参与
# 追觅科技求职进展汇总 #
18184次浏览 120人参与
# 今年秋招哪家公司给的薪资最良心? #
252642次浏览 1416人参与
# 实习想申请秋招offer,能不能argue薪资 #
149753次浏览 931人参与
# 如何KTV领导 #
62727次浏览 472人参与