正題

題目鏈接:https://www.luogu.com.cn/problem/CF183D

---

題目大意

$n$個人，$m$種衣服，給出每個人喜歡某件衣服的概率，你可以選擇$n$件衣服帶過去（可以重復款式）。求最大化能拿到喜歡衣服人的期望數量。

$1\le n\le 3000,1\le m\le 300$

---

解題思路

考慮暴力的$dp$，設$f_{i,j,k}$表示對于前$k$個人種類為$j$的衣服選擇了$i$件。

這樣顯然過不了。

但是考慮答案，假設我們第$i$種衣服選擇了$k$件那么產生的貢獻就是
$$\sum _{j=0}^{k}i\times f_{i,j,n}+k\sum _{j=k+1}^n{f}_{i,j,n}$$

然后對于$k?>k+1$會多產生的貢獻就是$1?{\sum }_{j=1}^k{f}_{i,j,n}$。考慮到這個值肯定是單調遞減的，所以貢獻函數是一個關于$k$的上凸函數。

然后就是很經典的方法了，每次暴力選擇一個能擴展的最大的擴展即可。

時間復雜度$O(n(n+m))$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int M=310,N=3100; 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 i=1;i<=m;i++)f[0][i][0]=1;for(int i=1;i<=n;i++)for(int j=1;j<=m;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 i=1;i<=m;i++){for(int j=1;j<=n;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 p=1;p<=n;p++){int pos=1;for(int i=2;i<=m;i++)if(s[i]<s[pos])pos=i;ans=ans+(1-s[pos]);s[pos]=s[pos]+f[k[pos]][pos][n];k[pos]^=1;int o=k[pos];for(int i=0;i<=n;i++)f[o][pos][i]=0;for(int i=1;i<=n;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; }

總結

以上是生活随笔為你收集整理的CF183D-T-shirtx【dp,贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。