题解 接力比赛
2021/10/3 6:40:04
本文主要是介绍题解 接力比赛,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门
完全没思路,并认为这个问题没有 \(O(n^2w)\) 以下的解法
遂糊了个暴力上去随便优化了一下,然后过了……
正解的话是random_shuffle构造随机数据,然后把第二个班看成负容量做背包
途中舍弃偏离0过远的决策,显然是对的而且没法卡
Code:
#include <bits/stdc++.h> using namespace std; #define INF 4485090715960753727ll #define N 100010 #define ll long long //#define int long long char buf[1<<21], *p1=buf, *p2=buf; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++) inline int read() { int ans=0, f=1; char c=getchar(); while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();} while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48), c=getchar(); return ans*f; } int n, m; ll w1[N], v1[N], w2[N], v2[N]; namespace force{ ll dp1[1000010], dp2[1000010], sum1, sum2, lim; void solve() { for (int i=1; i<=n; ++i) sum1+=w1[i]; for (int i=1; i<=m; ++i) sum2+=w2[i]; lim=min(sum1, sum2); memset(dp1, -0x3f, sizeof(dp1)); memset(dp2, -0x3f, sizeof(dp2)); dp1[0]=0; dp2[0]=0; int sum=0; for (int i=1; i<=n; ++i) { for (int j=sum; ~j; --j) { dp1[j+w1[i]]=max(dp1[j+w1[i]], dp1[j]+v1[i]); } sum+=w1[i]; } sum=0; for (int i=1; i<=m; ++i) { for (int j=sum; ~j; --j) { dp2[j+w2[i]]=max(dp2[j+w2[i]], dp2[j]+v2[i]); } sum+=w2[i]; } ll ans=0; for (int i=1; i<=lim; ++i) ans=max(ans, dp1[i]+dp2[i]); printf("%lld\n", ans); exit(0); } } signed main() { freopen("game.in", "r", stdin); freopen("game.out", "w", stdout); n=read(); m=read(); for (int i=1; i<=n; ++i) w1[i]=read(), v1[i]=read(); for (int i=1; i<=m; ++i) w2[i]=read(), v2[i]=read(); force::solve(); return 0; }
这篇关于题解 接力比赛的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)