@OceanEye7年前
05/4
19:49
期望DP
题目要求维护三次方
所以要把二次和一次的期望也给维护了，接着考虑我们DP的含义是什么。
DP[3][i]=DP[3][i-1] + (增长幅度=x^3-(x-1)^3)*(增长概率=p[i])
上面那个三次方展开一下就可以做了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define N 100010 double dp[4][N],_; int main() { int n; read(n); for(int i=1;i<=n;i++) { scanf("%lf",&_); dp[1][i]=(dp[1][i-1]+1)*_; dp[2][i]=(dp[2][i-1]+2*dp[1][i-1]+1)*_; dp[3][i]=dp[3][i-1]+(3*dp[2][i-1]+3*dp[1][i-1]+1)*_; } printf("%.1lf",dp[3][n]); return 0; } |