洛谷 1057_传球_dp

发布于 2019-05-08  817 次阅读


题目描述

有多少种不同的传球方法可以使得从小蛮手里开始传的球,传了m次以后,又回到小蛮手里。两种传球方法被视作不同的方法,当且仅当这两种方法中,接到球的同学按接球顺序组成的序列是不同的。比如有三个同学1号、2号、3号,并假设小蛮为1号,球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1,共2种。


思路

这题一看好像可以暴力,但好像会暴,所以机智的选择dp
f[i][j] 表示到第i个人在第j轮时有多少方法,然后dp方程:
f[i][j]=f[i-1][j-1]+f[i+1][j-1]
开头结尾特殊判断一下就可以了
O(nm)


#include 
int f[31][31];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    f[1][0]=1;
    for (int j=1;j<=m;j++)
        for (int i=1;i<=n;i++)
        {
            if (i==1)
                f[i][j]=f[2][j-1]+f[n][j-1];
            else if (i==n)
                f[i][j]=f[1][j-1]+f[n-1][j-1];
            else f[i][j]=f[i-1][j-1]+f[i+1][j-1];
        }
    printf("%d\n",f[1][m]);
}
]]>