期望DP | OceanEye's Blog

@OceanEye7年前

05/4

19:49

BZOJ4318

期望DP
题目要求维护三次方
所以要把二次和一次的期望也给维护了，接着考虑我们DP的含义是什么。
DP[3][i]=DP[3][i-1] + (增长幅度=x^3-(x-1)^3)*(增长概率=p[i])
上面那个三次方展开一下就可以做了

#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;
}

#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;

}

BZOJ4318

@OceanEye7年前

05/3

18:56

BZOJ1419

OceanEye 撰写 DP 数学期望DP 无回复

期望DP
和班上的一个物理大佬一起搞了二十分钟吧……然后发现这个期望(R,B)只和(R-1,B)以及(R,B-1)相关
然后就一个for循环再用一下滚动数组就可以了
dp[r][b]=(dp[r][b-1]-1)*b/(r+b) + (dp[r-1][b]+1)*r/(r+b)

#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;

int R,B;
double dp[2][5050];

#define now i&1
#define pre now^1

int main()
{
	read(R); read(B);
	for(int i=0;i<=B;i++)
	{
		for(int j=1;j<=R;j++) dp[now][j]=max(0.0,((dp[pre][j]-1)*((double)i/(i+j)))+((dp[now][j-1]+1)*((double)j/(i+j))));
	}
	printf("%.6f",dp[B&1][R]-5e-7);
	return 0;
}

#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;

int R,B;

double dp[2][5050];

#define now i&1

#define pre now^1

int main()

{

read(R); read(B);

for(int i=0;i<=B;i++)

{

for(int j=1;j<=R;j++) dp[now][j]=max(0.0,((dp[pre][j]-1)*((double)i/(i+j)))+((dp[now][j-1]+1)*((double)j/(i+j))));

}

printf("%.6f",dp[B&1][R]-5e-7);

return 0;

}

OceanEye's Blog

很多人即使只见过一面，已经算见过了最后一面。

@OceanEye7年前

BZOJ4318

BZOJ4318

@OceanEye7年前

BZOJ1419

BZOJ1419

友情链接

近期文章

标签