[JOI 2022 Final] 让我们赢得选举 (Let's Win the Election) / 選挙で勝とう (Let's Win the Election)
首先由
\[\min\left(\frac ab,\frac cd\right)\le\frac{a+c}{b+d}\le\max\left(\frac ab,\frac cd\right) \]得出，集中力量办大事，得到的支持者一定要和本人在同一州进行演讲。第二，为了尽量节约时间，在一个州的演讲时间只可能是 \(\boldsymbol{0,A_i,B_i}\) 三者之一。第三，一定是先演讲获得所有支持者。
所以有一个贪心：先将 \(B_i\) 为第一关键字、\(A_i\) 为第二关键字排序，贪心地选取。
但是会有一个问题：有些州 \(A_i\) 和 \(B_i\) 相差很大，我们舍弃 \(B_i\) 只演讲 \(A_i\) 的时间会更优。
这就不能靠贪心了，需要 DP。设 \(\mathit{dp}_{i,j}\) 为第 \(i\) 个州支持者数量为 \(j\) 时的答案，枚举 \(i\) 和支持者数量 \(j\)，对于前 \(i-1\) 个肯定要么选 \(A_i\)，要么选 \(B_i\)。有转移方程：
\[\mathit{dp}_{i,j}=\min\left(\mathit{dp}_{i-1,j}+\frac{A_i}{x+1},\mathit{dp}_{i-1,j-1}+\frac{B_i}j\right) \]其中 \(x\) 为总的支持者数量。结合代码理解。
#include<bits/stdc++.h>
using namespace std;
constexpr int MAXN=505;
int n,k,a[MAXN];
double ans=2e18,f[MAXN][MAXN];
struct P{
double a,b;
bool operator<(const P&x)const{
return b<x.b;
}
}p[MAXN];
double min(double a,double b){
return a<b?a:b;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(nullptr);
cin>>n>>k;
for(int i=1;i<=n;++i){
cin>>p[i].a>>p[i].b;
if(p[i].b==-1) p[i].b=2e18;
}
sort(p+1,p+n+1);
for(int x=0;x<=k;++x){
for(int i=1;i<=n;++i) a[i]=p[i].a;
for(int i=0;i<=n;++i)
for(int j=0;j<=n;++j)
f[i][j]=2e18;
f[0][0]=0;
double res=2e18;
for(int i=1;i<=n;++i)
for(int j=0;j<=min(x,i);++j){
f[i][j]=f[i-1][j]+p[i].a/(x+1);
if(j&&p[i].b<2e18) f[i][j]=min(f[i][j],f[i-1][j-1]+p[i].b/j);
}
for(int i=k;i<=n;++i) res=min(res,f[i][x]);
for(int i=k;i>=x;--i){
sort(a+i+1,a+n+1);
double sm=0;
for(int j=i+1;j<=k;++j) sm+=a[j];
res=min(res,f[i][x]+sm/(x+1));
}
ans=min(ans,res);
}
cout<<fixed<<setprecision(15)<<ans<<'\n';
return 0;
}