Java教程

题解 接力比赛

本文主要是介绍题解 接力比赛，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门

完全没思路，并认为这个问题没有 \(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;
}
这篇关于题解 接力比赛的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航