坪地网站建设怎么样,从事网站开发的想考研,建筑图纸字母代号大全图解,外贸网站违反谷歌规则正题
题目链接:https://www.luogu.com.cn/problem/CF183D 题目大意 nnn个人#xff0c;mmm种衣服#xff0c;给出每个人喜欢某件衣服的概率#xff0c;你可以选择nnn件衣服带过去#xff08;可以重复款式#xff09;。求最大化能拿到喜欢衣服人的期望数量。 1≤n≤3000,1…正题
题目链接:https://www.luogu.com.cn/problem/CF183D 题目大意
nnn个人mmm种衣服给出每个人喜欢某件衣服的概率你可以选择nnn件衣服带过去可以重复款式。求最大化能拿到喜欢衣服人的期望数量。
1≤n≤3000,1≤m≤3001\leq n\leq 3000,1\leq m\leq 3001≤n≤3000,1≤m≤300 解题思路
考虑暴力的dpdpdp设fi,j,kf_{i,j,k}fi,j,k表示对于前kkk个人种类为jjj的衣服选择了iii件。
这样显然过不了。
但是考虑答案假设我们第iii种衣服选择了kkk件那么产生的贡献就是 ∑j0ki×fi,j,nk∑jk1nfi,j,n\sum_{j0}^k i\times f_{i,j,n}k\sum_{jk1}^nf_{i,j,n}j0∑ki×fi,j,nkjk1∑nfi,j,n
然后对于k−k1k-k1k−k1会多产生的贡献就是1−∑j1kfi,j,n1-\sum_{j1}^kf_{i,j,n}1−∑j1kfi,j,n。考虑到这个值肯定是单调递减的所以贡献函数是一个关于kkk的上凸函数。
然后就是很经典的方法了每次暴力选择一个能扩展的最大的扩展即可。
时间复杂度O(n(nm))O(n(nm))O(n(nm)) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int M310,N3100;
int n,m,k[M];double s[M],f[2][M][N],a[M][N],ans;
int main()
{scanf(%d%d,n,m);for(int i1;im;i)f[0][i][0]1;for(int i1;in;i)for(int j1;jm;j){scanf(%lf,a[j][i]);a[j][i]/1000.0;f[0][j][i]f[0][j][i-1]*(1-a[j][i]);}for(int i1;im;i){for(int j1;jn;j)f[1][i][j]f[1][i][j-1]*(1-a[i][j])f[0][i][j-1]*a[i][j];k[i]1;s[i]f[0][i][n];}for(int p1;pn;p){int pos1;for(int i2;im;i)if(s[i]s[pos])posi;ansans(1-s[pos]);s[pos]s[pos]f[k[pos]][pos][n];k[pos]^1;int ok[pos];for(int i0;in;i)f[o][pos][i]0;for(int i1;in;i)f[o][pos][i]f[o][pos][i-1]*(1-a[pos][i])f[!o][pos][i-1]*a[pos][i];}printf(%.12lf\n,ans);return 0;
}
