【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+10;

double dp[maxn][maxn];
void init()
{

    for(int i=0;i<maxn;i++)
    {
        for(int k=0;k<maxn;k++)
        {
            dp[i][k]=-1;
        }    
    }
    dp[0][0]=log(1.0);
    for(int i=0;i<maxn;i++)
    {
        for(int k=0;k<maxn;k++)
        {
            if(i>k)
            {
                if(dp[i-1][k]!=-1&&dp[i][k-1]!=-1)
                {
                    dp[i][k]=dp[i-1][k]+log(1+exp(dp[i][k-1]-dp[i-1][k]));    
                }    
                else if(dp[i-1][k]!=-1)
                {
                    dp[i][k]=dp[i-1][k];
                }
                else if(dp[i][k-1]!=-1)
                {
                    dp[i][k]=dp[i][k-1];
                }
            }    
        }
    }
}
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=1;kas<=T;kas++)
    {
        scanf("%d%d",&n,&m);
        double ans=0;
        for(int i=1;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);
    }    
}

View Code

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

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

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

推荐阅读