【DP系列学习一】简单题：kickstart2017 B.vote

https://code.google.com/codejam/contest/6304486/dashboard#s=p1

这是一道简单的dp,dp[i][j]代表A的voter为i,B的voter为j时的成功方案数，转移方程是dp[i][j]=dp[i-1][j]+dp[i][j-1],这里一定满足i>j,(由题意，不管何时，A都要赢),所以初始化dp[i][j]为-1,dp[0][0]=1;

这道题要注意的地方是：由于数据范围是2000,2000！非常大，所以要取对数，这是乘除对应变成加法，加法可转化为：c=log(e^a+e^b)->c=log(e^a(1+e^(b-a)))=a+log(1+e^(b-a)) 这样就不会溢出了.

以下是我的代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#define eps 1e-8

#include<cmath>

using namespace std;

const int maxn=2e3+;

double dp[maxn][maxn];

void init()

{

    for(int i=;i<maxn;i++)

    {

        for(int k=;k<maxn;k++)

        {

            dp[i][k]=-;

        }

    }

    dp[][]=log(1.0);

    for(int i=;i<maxn;i++)

    {

        for(int k=;k<maxn;k++)

        {

            if(i>k)

            {

                if(dp[i-][k]!=-&&dp[i][k-]!=-)

                {

                    dp[i][k]=dp[i-][k]+log(+exp(dp[i][k-]-dp[i-][k]));

                }

                else if(dp[i-][k]!=-)

                {

                    dp[i][k]=dp[i-][k];

                }

                else if(dp[i][k-]!=-)

                {

                    dp[i][k]=dp[i][k-];

                }

            }

        }

    }

}

int main()

{

//    freopen("B-large-practice.in","r",stdin);

//    freopen("data.out","w",stdout);

    init();

    int T;

    scanf("%d",&T);

    int n,m;

    for(int kas=;kas<=T;kas++)

    {

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

        double ans=;

        for(int i=;i<=m;i++)

        {

            ans+=(double)log(i)-(double)log(n+i);

        }

        ans+=(double)dp[n][m];

        ans=exp(ans);

    //    ans+=eps;

        printf("Case #%d: %.8f\n",kas,ans);

    }

}

另外，这道题的答案其实就是(n-m)/n+m可以这样理解：

http://blog.csdn.net/febr2/article/details/55846416

巴特西

【DP系列学习一】简单题：kickstart2017 B.vote

最新文章

热门文章