CF183D T-shirt

痛定思痛。 2021-12-04 05:53 170阅读 0赞

[http://codeforces.com/problemset/problem/183/D][http_codeforces.com_problemset_problem_183_D]

### 题解 ###

我们可以对于每种\\(size\\)的\\(T-shirt\\)，设计一个\\(dp\\)。

令\\(dp\[i\]\[j\]\\)表示这种\\(T-shirt\\)准备\\(i\\)件，转移到了第\\(j\\)个人，有\\(i\\)个人喜欢这种\\(T-shirt\\)的概率。

转移：

\\(dp\[i\]\[j\]=dp\[i-1\]\[j-1\]\*p\[j\]\[now\]+dp\[i\]\[j-1\]\*(1-p\[j\]\[now\]\\)

最后我们把恰好转成至少，根据期望的线性性，取最大的前\\(n\\)个好了。

但是复杂度无法接受，因为我们只需要取前\\(n\\)个，所以可以贪心的选取最大的种类，从\\(dp\[i\]\[j\]\\)扩展到\\(dp\[i+1\]\[j\]\\)。

### 代码 ###

#include<bits/stdc++.h> #define N 3002 #define M 302 using namespace std; typedef long long ll; int n,m; long double dp[M][N],ans,pre[N],p[N][M],now[M]; inline ll rd(){ ll x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } int main(){ n=rd();m=rd(); for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j)p[i][j]=(double)rd()/1000.0; } for(int i=1;i<=m;++i){ dp[i][0]=1; for(int j=1;j<=n;++j)dp[i][j]=dp[i][j-1]*(1-p[j][i]); now[i]=1-dp[i][n]; } for(int i=1;i<=n;++i){ int k=0; for(int j=1;j<=m;++j)if(now[j]>now[k])k=j; if(!k)break; ans+=now[k]; swap(pre,dp[k]); dp[k][0]=0; for(int j=1;j<=n;++j)dp[k][j]=pre[j-1]*p[j][k]+dp[k][j-1]*(1-p[j][k]); now[k]-=dp[k][n]; } // printf("%.12Lf",ans);//laji cout<<fixed<<setprecision(10)<<ans<<endl; return 0; }

转载于:https://www.cnblogs.com/ZH-comld/p/11096252.html

[http_codeforces.com_problemset_problem_183_D]: http://codeforces.com/problemset/problem/183/D

发表评论取消回复

表情：

评论列表（有 0 条评论，170人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF1214D

CF1214D 题意： > 给你一个 $ n \\times m $ 的矩阵，求最少用多少个障碍，将 $ (1,1) $ 到 $ (n,m) $ 的路径堵死...

た入场券/ 2024年04月20日 10:34/ 0 赞/ 97 阅读

相关 CF981D

CF981D 题意： > 给你n个数，要求你分成k堆。每堆的内部加和，每堆之间是相与。问最大的值。解法： > 二进制下最大的数的所有位一定是1，所...

缺乏、安全感/ 2024年04月20日 10:26/ 0 赞/ 91 阅读

相关 CF427D

CF427D > SA的奇技淫巧，其实就是板子。题意： > 给定两个字符串，求最短的满足各只出现一次的连续公共字串解析： > 一般情况下，SA...

素颜马尾好姑娘i/ 2024年04月20日 10:25/ 0 赞/ 90 阅读

相关 CF1208D

CF1208D 题意； > 给你一个数组，要求支持单点修改和单点查询解法： > 直接线段树搞一搞就没了。 CODE： includ...

系统管理员/ 2024年04月20日 10:24/ 0 赞/ 97 阅读

相关【贪心】CF1841 D

[Codeforces][] 题意： ![f231a62f84944973acc878c8bcd43a09.png][] ![eed5aa21f67e4bf8a27aad

绝地灬酷狼/ 2024年03月23日 23:24/ 0 赞/ 70 阅读

相关【构造】CF1798 D

[Problem - D - Codeforces][] 题意： ![ee9f61a4f71440ea8d521c072445781b.png][] 思路：首先如果

超、凢脫俗/ 2024年03月23日 20:15/ 0 赞/ 95 阅读

相关【构造】CF1758 D

[Problem - D - Codeforces][] 题意： ![0f1d5284e9964d37a6889cff4db258a4.png][] 思路：如果需要构

亦凉/ 2024年03月22日 23:16/ 0 赞/ 64 阅读

相关 D. AB-string——CF1238D

https://codeforces.com/problemset/problem/1238/D 思路： 1、每个字符存在回文串的最地条件是： AA ， BB， ABA

小灰灰/ 2023年06月06日 10:35/ 0 赞/ 26 阅读

相关 CF1110D Jongmah

题意给出\\(n\\)个在\\(1\\)到\\(m\\)范围内的数\\(a\_i\\)，定义一个三元组为\\((x,x,x)\\)或者\\((x,x+1,x+2)\\)

深藏阁楼爱情的钟/ 2022年01月12日 09:29/ 0 赞/ 223 阅读

相关 CF183D T-shirt

[http://codeforces.com/problemset/problem/183/D][http_codeforces.com_problemset_problem_

痛定思痛。/ 2021年12月04日 05:53/ 0 赞/ 171 阅读