HDK: 他妈的，这个看着也不像 2900 啊，为啥控我这么久
lbtl: 他不控你这么久不就不是 2900 了吗
暴力
一个比较明显的暴力思路是，如果我们钦定选定的物品的价值，那么可以比较容易地由背包 DP 算出能达到这个钦定值的最大概率
从 \([0,\sum w_i]\) 枚举所有可能的价值，暴力跑若干次背包，可以通过高达六个测试点
暴力
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int p[200001],w[200001];
long double f[200001];
signed main(){
cin>>n;
int totw=0;
for(int i=1;i<=n;++i){
cin>>p[i]>>w[i];
totw+=w[i];
}
long double ans=0;
for(int i=1;i<=totw;++i){
for(int j=0;j<=i;++j){
f[j]=0;
}
for(int j=1;j<=n;++j){
for(int k=i;k>=w[j];--k){
f[k]=max(f[k],f[k-w[j]]*p[j]/100.0);
}
f[w[j]]=max(f[w[j]],(long double)p[j]/100.0);
}
ans=max(ans,f[i]*i);
}
printf("%.8Lf",ans);
}
优化
一个比较 naive 的优化是，你发现你根本就不用钦定选定价值，直接跑一遍背包就能把所有答案跑出来，但是因为太 naive 了，仍然只有六个测试点的高分
第一个优化是对我们枚举上界的优化
推一遍式子，考虑设当前 \(\sum \frac{p_i}{100}=x,\sum w_i=y\)
当加入物品 \((p,w)\) 时对答案有正贡献，当且仅当
\[\begin{aligned}xy&\lt x\times \frac{p}{100}\times (y+w)\\y&\lt \frac{p}{100}(y+w)\\(1-\frac{p}{100})y&\lt\frac{p}{100}w\\y&\lt\frac{pw}{100-p}\end{aligned} \]由于题目规定 \(pw\le 2\times 10^5\)，而 \(100-p\) 的下界是 \(1\)，因此加入物品 \((p,w)\) 时对答案有正贡献的一个必要条件是 \(\sum\limits w_i\le 2\times 10^5\)
这样我们就将答案区间 从 \([0,\sum w_i]\) 降到 \([0,2\times 10^5]\) 了
但是
喜报，复杂度还是不对
我们再考虑其他两个优化
第二个优化是，我们贪心地想，选择 \(p_i=100\) 的 \(i\) 一定是最优的，因此我们可以提前将 \(p_i=100\) 的 \(i\) 全部选上，这样既压缩了答案区间也减少了物品数量
第三个优化是，我们观察剩下的 \(p_i\neq 100\) 的物品，如果我们将 \(p_i\) 相同的 \(i\) 分成同一组，并且让每一组内按照 \(w_i\) 降序排列，根据贪心思路，当 \(p\) 相同的时候，应该是 \(w\) 越大越好，最终答案一定是形如从每个 \(p_i\) 的组内选出一个前缀
和刚才的思路类似，现在我们钦定我们选择的物品的 \(p_i\) 都为 \(p\)，如果我们给当前 \(p\) 选择的前缀长度从 \(k\) 增加到 \(k+1\)，答案更优当且仅当（这里挂 \(100\) 太麻烦了，在下面几个式子里钦定 \(p=\frac{p_i}{100}\)）
\[\begin{aligned}p^k\times \sum\limits_k w\lt p^{k+1}\times(w_{k+1}+\sum\limits_k w)\end{aligned} \]由于新加入的 \(w_{k+1}\) 不大于已有的任何一个数，因此有 \(k\times w_{k+1}\le\sum\limits_k w_i\)，因此
\[\begin{aligned}p^k\times \sum\limits_k w&\le p^{k+1}\times\frac{k+1}{k}\times\sum\limits_k w_i\\\frac{k+1}{k}&\lt p\\k+1&\lt k\times p\\k\lt \frac{1}{1-p}\end{aligned} \]这个式子意味着只有前 \(\frac{1}{1-p}\) 个物品有可能成为最优解
赛时止步于只写了两个优化，并且发现了最后那个先增后减的单调性，但是没总结出最后一个结论，比较可惜
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int p[200001],w[200001];
struct item{
int w,p;
}a[200001];
int cnt=0;
long long orians;
long double f[200001];
long double ans;
vector<int>v[101];
signed main(){
cin>>n;
for(int i=1;i<=n;++i){
cin>>p[i]>>w[i];
v[p[i]].push_back(w[i]);
if(p[i]==100) orians+=w[i];
}
for(int i=1;i<=100;++i){
sort(v[i].begin(),v[i].end(),greater<int>());
}
for(int i=1;i<=99;++i){
int tot=0;
for(int j=0;j<=(int)v[i].size()-1;++j){
if(tot>100/(100-i)) break;
a[++cnt]={v[i][j],i};
tot++;
}
};
f[0]=1;
for(int i=1;i<=cnt;++i){
for(int j=200000;j>=a[i].w;--j){
f[j]=max(f[j],f[j-a[i].w]*a[i].p/100.0);
}
}
for(int i=0;i<=200000;++i){
ans=max(ans,f[i]*(orians+i));
}
printf("%.8Lf",ans);
}