题面
小迟最近去参加了一个锦标赛，这个锦标赛总共有 n 轮比赛，最终成绩由这 n 轮比赛中赢的轮数决定。由于小迟每轮比赛的胜利概率，则取决于他在该轮比赛之前的战绩。也就是说，如果小迟在第 i 轮比赛选择积极应战，并且前 i-1 轮比赛中取得了 j 胜的话，那么第 i 轮比赛的胜率概率为p[i][j]，这里我们保证了一点就是对于同一个 i，p[i][j] 关于 j 的上升保持调不上升（也就是说 p[i][j]>p[i][j+1])。小迟观察到这个规则之后，想到了一个可能可以使他最终成绩更优的方法，就是在某些轮比赛采取第2种策略，故意求败，也就是以 100% 的概率输掉该轮比赛，从而使自己在后面能够遇到更容易对付的对手。
小迟现在已经看到了整个 p 数组，小迟希望你能告诉他一个最优的策略，使得他能最大化他的期望赢的轮数。
分析
其实放水只是个烟雾弹，小数据其实是在疯狂暗示你，放水一定不会更优。
拿2轮比赛举例子 假设p0是赢第1轮的概率，p1是赢第1轮后赢第2轮的概率，p2是没赢第一轮却赢第2轮的概率
不放水的期望：p0*p1*2+p0*(1-p1)+(1-p0)*p2=p0*(1+p1-p2)+p2
放第一轮的水的期望：p2
放第二轮的水的期望：p0
作差比较，一式减二式得 p0*(1+p1-p2)显然>=0 一式减三式得 p0*(p1-p2)+p2=p0*p1+p2*(1-p0) 显然>=0
所以无论怎么放水，都不会比不放水优秀
因此我们只需要做一个dp就好了，期望和概率都可以，这里是正着做就是概率dp
前i+1场中赢j+1场的概率+=前i+1场中赢j场的概率*本场赢的概率
前i+1场中赢j场的概率+=前i+1场中赢j场的概率*本场输的概率
最后算一下期望就好了
代码
#include<bits/stdc++.h> using namespace std; #define N 1010 #define db double int n; db ans,f[N][N],p[N][N]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=0;j<i;j++) scanf("%lf",&p[i][j]); f[0][0]=1; for(int i=0;i<n;i++) for(int j=0;j<=i;j++) { f[i+1][j+1]+=f[i][j]*p[i+1][j]; f[i+1][j]+=f[i][j]*(1-p[i+1][j]); } for(int i=0;i<=n;i++)ans+=f[n][i]*i; printf("%.2lf",ans); return 0; }