【DP水题】投票问题（二）

【DP水题】投票问题（二）

投票问题（一）

【试题描述】

欧阳文和欧阳武竞选学联主席，汪梁森负责唱票，共有m+n张，结果欧阳文获胜，已知欧阳文和欧阳武分别获得 m 张票和 n 张票（m>n）。

现在请你计算在唱票过程中欧阳文的票数始终比欧阳武票数多的方案有多少种。

【输入要求】

一行，包括两个数，分别为 m 和 n

【输出要求】

一个数，表示符合题目要求的方案数。

【输入实例】

2 1

　　

【输出实例】

1

　　

【其他说明】

数据范围：1 <= m,n < 100.

【试题分析】

比投票问题（一）是不是范围加大了许多？？虽然DFS不能过了，但是用DP还是水的不行，我们来直接看代码

【代码】

#include<iostream>

using namespace std;

inline int read()

{

    int x,f=1;

    char ch=getchar();

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;

    for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0');

    return x*f;

}

inline void write(int x){

    if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;

    int len=0,buf[15];while(x)buf[len++]=x%10,x/=10;

    for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;

}

long long dp[100][100];

int a,b,m,n;

int main()

{

    n=read(),m=read();

    if(m>=n) {cout<<0;return 0;} //不符合条件，其实木有不符合的 QAQ

    dp[1][0]=1;

    for(a=2;a<=n;a++)

        for(b=0;b<a&&b<=m;b++)

        {

            if((b==m||b==a-1)&&a==n)dp[a][b]=dp[a-1][b]+dp[a][b-1]+1;

            else dp[a][b]=dp[a-1][b]+dp[a][b-1];

        }

    write(dp[n][m]-1);

}