绍兴游记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;
}
完结撒花✿✿ヽ(°▽°)ノ✿