UVA-1498 Activation

UVA-1498

UVA-1498  ActivationUVA-1498  Activation

  

  DP应该是肯定的,设 f [ i ] [ j ] 表示现在对*有 i 人,Tomato在第 j 个,我们可以很(简单的)艰难的列出下列方程:

     f[i][1] = p1*f[i][1] + p2*f[i][i] + p4
     f[i][j]
= p1*f[i][j] + p2*f[i][j-1] + p3*f[i-1][j-1] + p4 (2<=j<=k)
     f[i][j]
= p1*f[i][j] + p2*f[i][j-1] + p3*f[i-1][j-1] (j>k)

  (由于我们是在求第 i 项,所以第 i - 1 项是已知量)

  然后化简可得:

    令  a=p2/(1.0-p1) , b=p3/(1.0-p1) , c=p4/(1.0-p1)

    f[i][
1] = a*f[i][i] + c
    f[i][j]
= a*f[i][j-1] + b*f[i-1][j-1] + c (2<=j<=k)
    f[i][j]
= a*f[i][j-1] + b*f[i-1][j-1] (j>k)

  再代入一(亿)下,可以求出 f [ i ] [ 1 ] 的表达式。

  所以,我们先求出  [ i ] [ 1 ] ,然后就可以求出剩下的值了。

 

  但是,这玩意怎么初始化呢?

  YY一哈可以发现:

  f[1][1] = a*f[1][1] + c
       = c / (1-a)

  之后就水到渠成了。

  最后YY一哈,有特判!有特判!有特判!(可能出现除数为 0 的情况)(调了一个晚上,~qwq~)(具体见Code)

 

  Code:

UVA-1498  Activation
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define Zero(x) (((x)>0?(x):-(x))<1e-10)
using namespace std;
int n,m,K;
double p1,p2,p3,p4,a,b,c,Inv[2005],f[2][2005];
int main()
{
    while(scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&K,&p1,&p2,&p3,&p4)!=EOF)
    {
        if(Zero(p1+p2-1)==1) {printf("0.00000\n");continue;}
        p1=1.0-p1,a=p2/p1,b=p3/p1,c=p4/p1,Inv[0]=1;
        for(register int i=1;i<=n;++i) Inv[i]=Inv[i-1]*a;
        for(register int i=1;i<=n;++i)
        {
            f[i&1][1]=c;
            for(register int j=2;j<=min(i,K);++j) f[i&1][1]+=(b*f[(i-1)&1][j-1]+c)*Inv[i-j+1];
            for(register int j=K+1;j<=i;++j) f[i&1][1]+=b*f[(i-1)&1][j-1]*Inv[i-j+1];
            f[i&1][1]/=(1-Inv[i]);
            for(register int j=2;j<=min(i,K);++j) f[i&1][j]=a*f[i&1][j-1]+b*f[(i-1)&1][j-1]+c;
            for(register int j=K+1;j<=i;++j) f[i&1][j]=a*f[i&1][j-1]+b*f[(i-1)&1][j-1];
        }
        printf("%.5lf\n",f[n&1][m]);
    }
    return 0;
}
View Code

 

UVA-1498 Activation

上一篇:web离线应用 Web SQL Database


下一篇:MYSQL的慢查询分析