绍兴游记Day1 b 题解

绍兴游记Day1 b 题解

题面

【问题描述】

ξ成为了赛车手，但是她发现她没有实战经验。每参加一场赛车比赛她会获得a_i的经验，假设参加完这场比赛后她的总经验是E，那么她会获得E ∗ b_i的奖金。 ξ要参加的比赛场数是偶数，在参加完恰好一半的比赛后她会参加一个夏令营去练习飙车，这次夏令营会给她X点经验但是没有奖金。 ξ想知道如何合理安排参加比赛的顺序可以使得获得的奖金最多？你需要求出奖金的最大值。

【输入格式】

从文件 b.in 中读入数据。 第一行两个正整数n, X。 第二行n个正整数a_i。 第三行n个正整数b_i。

【输出格式】

输出到文件 b.out 中。 一行一个整数表示能够获得的最大奖金。

【样例输入】

2 10 1 1 1 5

【样例输出】

61

【数据规模】

对于20%的数据，n ≤ 10。 对于40%的数据，n ≤ 20。 另有10%的数据，b_i = 1。 另有10%的数据，a_i = 1。 对于100%的数据，n ≤ 50, 1 ≤ a_i ≤ 10^5, 1 ≤ b_i ≤ 10, 0 ≤ X ≤ 10^5, n是偶数。

题解

贪心

可以先考虑把所有比赛按照奖金贡献进行排序，最关键的就是如何排序、如何比较两场比赛的奖金贡献大小。

交换前：

交换后：

所以，我们可以事先求出\frac{a_i}{b_i}然后再按照\frac{a_i}{b_i}从大到小排序。

DP

因为b小a大，所以状态中只能记录有关b的那一部分。直接DP很难做到这样的效果，如果要只和b有关就必须支付更多的复杂度计算一些冗余状态以达到不重不漏的目的。 不妨直接大胆枚举后一半的b之和，然后在计算出的结果中只挑选b之和等于所枚举的答案的那一部分。

设f[i][j][k]前i个比赛j个在前面i-j个在后面，在前面的b之和为k时的最大收益。 f[i+1][j+1][k+a[i].b]=max(f[i][j][k]+k*a[i].a) 选择在前面，比赛数量i+1，选择在前面j+1，前面的b之和k+a[i].b，转移：从该比赛再加上之前的比赛的b之和乘上a[i].a f[i+1][j][k]=max(f[i][j][k]+(sum[i-1]-k)*a[i].a+p*a[i].a) 选择在后面，比赛数量i+1，选择在后面j不变，前面的b之和k不变，转移：从该比赛再加上之前的比赛的b之和（后面的）乘上a[i].a 还有中途的X记得要加上：ans=max(ans,f[n+1][n/2][p]+p*X) 最后还要把n个比赛的基本奖金加上：for(int i=1;i<=n;i++) ans+=a[i].a*a[i].b

Code

#include<bits/stdc++.h> #define inf 2e9 using namespace std; int n,X,E,ans,vis[55],f[55][55][550],sum[55]; inline int read(){ char ch=getchar();int res=0,f=1; while(ch<’0’ch>’9’){if(ch==’-‘)f=-1;ch=getchar();} while(ch>=’0’&&ch<=’9’) res=res*10+ch-‘0’,ch=getchar(); return res*f; } struct node{ int a,b; double c; }a[55]; bool cmp(node qx,node qy){ return qx.c>qy.c; } int main(){ //freopen(“b.in”,”r”,stdin);freopen(“b.out”,”w”,stdout); n=read();X=read(); for(int i=1;i<=n;i++) a[i].a=read(); for(int i=1;i<=n;i++) a[i].b=read(); for(int i=1;i<=n;i++) a[i].c=(double)a[i].a/(double)a[i].b;//计算出sort比较系数 sort(a+1,a+n+1,cmp);//排序 for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i].b; for(int p=n/2;p<=10*(n/2);p++){//枚举前面的比赛的b之和 for(int i=2;i<=n+2;i++)//第一场比赛不能清（用来dp初始），因为下面下标会加一，所以多清空一个 for(int j=0;j<=i-1;j++)//前面的比赛数量 for(int k=j;k<=j*10;k++) f[i][j][k]=-inf;//前面的b之和，清空 for(int i=1;i<=n;i++){ for(int j=0;j<=i-1;j++){ for(int k=j;k<=j*10;k++){ if(f[i][j][k]>=0){//初始状态 f[i+1][j+1][k+a[i].b]=max(f[i][j][k]+k*a[i].a,f[i+1][j+1][k+a[i].b]);//放在前面 f[i+1][j][k]=max(f[i+1][j][k],f[i][j][k]+(sum[i-1]-k)*a[i].a+p*a[i].a);//放在后面 } } } } ans=max(ans,f[n+1][n/2][p]+p*X);//不要忘记二分之一的n时的经验X } for(int i=1;i<=n;i++) ans+=a[i].a*a[i].b;//不要忘记基本的奖学金 printf(“%d\n”,ans);return 0; }

完结撒花✿✿ヽ(°▽°)ノ✿