P7642 [BalticOI 2006 Day 2] JUMP THE BOARD! 题解

· · 题解

题目大意

给定一个 n \times n 的方格，只能从下或从右移动当前格子上的数那么多的步数，求出从左上角到右下角的方案数。

思路

对于求方案数的题目，不难发现这是一道 dp 题。状态转移方程也非常好推。

设 dp[i][j] 表示现在在第 i 行第 j 列时的方案数，由题意得：

\begin{Bmatrix}dp[i+g[i][j]][j]+=dp[i][j],i+g[i][j]≤n\\dp[i][j+g[i][j]]+=dp[i][j],j+g[i][j]≤n\end{Bmatrix}

其中边界为 dp[1][1]=1,答案为 dp[n][n]。

但是，我们发现题目的数据范围极大，不得不用高精度。

于是——人生苦短，我用 python!

code

dp=[]
g=[]
for i in range(0,110):
    dp.append([])
    g.append([])
    for j in range(0,110):
        dp[i].append(0)
n=int(input())
for i in range(1,n+1):
    g[i]=input().split()
    g[i].append(int(g[i][n-1]))
    for j in range(n-1,0,-1):
        g[i][j]=int(g[i][j-1])

dp[1][1]=1
g[n][n]=1
for i in range(1,n+1):
    for j in range(1,n+1):
        if(i+g[i][j]<=n):
            dp[i+g[i][j]][j]+=dp[i][j]
        if(j+g[i][j]<=n):
            dp[i][j+g[i][j]]+=dp[i][j]
print(dp[n][n])