URAL 1776 Anniversary Firework （概率,区间DP）

坑，一开始以为，分成两半的时候去最大那个就行了，

实际上这样是不对的，因为有可能出现小的一半的时间比大的要长，

因为还和等待次数有关，且转移的时候需要用到次数更小的状态，

所以状态定义为二维，dp[i][j]表示长度为i的区间，放小于等于j次的概率。

要求确切的某次的概率，比如k，就只要用dp[i][k]-dp[i][k-1]就行了。

如何转移？从小到大枚举i，从小到大枚举j，初始化dp[i][j] = dp[i][j-1]，

然后求出确切等待j次的概率，以k为界限划分区间，分成l,r两段，加上l区间等待j-1次且r区间等待小于等于j-1次的概率，

类似得加上r区间等待j-1次且l区间等带小于等于j-1次的概率，然后减掉重复计算的状态。

因为只要求中间等待的次数，且一开始要放两个鞭炮，所以可以等效为一开始不计等待，之后每次都计算等待时间。

还有一个细节是每次j从2开始枚举，放一次的只可能是长度为1的情况。

g++使用%lf正常，但在有些oj却会出问题

#include<bits/stdc++.h>

using namespace std;

const int maxn = ;

double dp[maxn][maxn];

int main()

{

    //freopen("in.txt","r",stdin);

    int n; scanf("%d",&n);

    n -= ;

    for(int i = ; i <= n; i++){

        for(int j = i; j <=n; j++)

             dp[i][j] = ;

    }

    for(int i = ; i <= n; i++){

        double e = ./i;

        for(int j = ; j < i; j++){

            dp[i][j] = dp[i][j-];

            for(int k = ; k <= i; k++){

                int l = k-,r = i-k;

                double p1 = dp[l][j-] - dp[l][j-], p2 = dp[r][j-] -  dp[r][j-];

                double p3 = dp[l][j-];

                double p4 = dp[r][j-];

                dp[i][j] += e*(p1*p4 + p2*p3 - p2*p1);

            }

        }

    }

    double ans = ;

    for(int i = ; i <= n; i++){

        ans += (dp[n][i]-dp[n][i-])*i*;

    }

    printf("%.11lf\n",ans);

    return ;

}

巴特西

URAL 1776 Anniversary Firework （概率,区间DP）

最新文章

热门文章