题目大意
有\(n\)个二元组\((p_i,w_i)\)，保证\(1\le p_i\le100,p_iw_i\le200000\)，求一个集合\(S\)，使得\(\prod_{i\in S}\frac{p_i}{100}\sum_{i\in S}w_i\)最大
题解
考虑一个极大的集合有什么样的性质，所谓极大就是不能够通过加入一个元素使得答案更大
设集合为\(S\)，则不存在\(k\not\in S\)，使得\(\sum_{i\in S}w_i\prod_{i\in S}\frac{p_i}{100}<(\sum_{i\in S}w_i+w_k)\prod_{i\in S}\frac{p_i}{100}\frac{p_k}{100}\)
作一些化简，得到\(\sum_{i\in S}w_i<\frac{p_kw_k}{100-p_k}\)，此时加入\(k\)会使答案变大，反之使答案减小，那么可以观察到\(\sum_{i\in S}w_i\le \frac{99*w}{100-99}=200000\)，也就是答案的集合的\(w\)和小于等于\(200000\)，这样就可以想到使用背包解决，但复杂度依旧爆炸
可以按\(p\)分类每个二元组，然后按\(w\)从大到小排序，选择的集合显然是排序后的一个前缀，由前面推导的结论，如果选择放入第\(i\)个二元组，有一个必要条件\(\sum_{j=1}^{i-1}w_j<\frac{pw_i}{100-p}\)，放缩一下\(iw_i<\frac{pw_i}{100-p}\)，得到\(i<\frac{p}{100-p}\)
所以对于一个\(p\)，最多只用做\(\lfloor\frac{p}{100-p}\rfloor\)次背包
\(p=1\sim 99\)，得到运算次数约为\(400\)次，做\(400\)次背包，可以通过
代码
点击查看代码
#include<cstdio>
#include<vector>
#include<algorithm>
#define db double
using namespace std;
const int P=100,W=200000;
int n;
vector<int> w[P+10];
bool cmp(int a,int b){return a>b;}
db f[W+10];
void solve(int p,int w)
{for(int i=W;i>=w;i--)f[i]=max(f[i],f[i-w]*p/100);
}
int main()
{f[0]=1;scanf("%d",&n);for(int i=1,p,x;i<=n;i++){scanf("%d %d",&p,&x);w[p].push_back(x);}for(int i=1;i<P;i++){sort(w[i].begin(),w[i].end(),cmp);int resw=0;for(int j:w[i]){if(resw*(100-i)>=i*j)break;solve(i,j);resw+=j;}}db ans=0;int sumw=0;for(int j:w[P]) sumw+=j;for(int i=0;i<=W;i++)ans=max(ans,f[i]*(sumw+i));printf("%.8lf",ans);return 0;
}
