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

· · 题解

题目传送门

如果不用高精是一道简单的 DP 题。

设 f_{i,j} 表示走到第 i 行第 j 列的总方案数，val_{i,j} 表示第 i 行第 j 列的步长。

对于每个格子 (i,j) 接下来走的路只有两种可能：从 (i,j) 走到 (i+val_{i,j},j) ；从 (i,j) 走到 (i,j+val_{i,j}) 。于是可以依此写出状态转移方程：

f_{i+val_{i,j},j} \gets \sum f_{i,j} f_{i,j+val_{i,j}} \gets \sum f_{i,j}

值得注意的是，对于 val_{i,j} = 0 的点是死胡同，需要特判。还有答案可能较大，需要使用高精。

AC Code:

#include<bits/stdc++.h>
using namespace std;
const int MAXN=101;

struct Number{
    int arr[MAXN],len;
}f[MAXN+10][MAXN+10];
int n,val[MAXN][MAXN];

void print(Number x){
    for (int i=MAXN-x.len;i<MAXN;i++)
        cout<<x.arr[i];
    cout<<endl;
}
Number new_number(){
    Number x;
    x.len=1;
    memset(x.arr,0,sizeof(x.arr));
    return x;
}
Number number_add(Number x,Number y){
    int p=0;
    for (int i=MAXN-1;i>=MAXN-max(x.len,y.len)||p;i--){
        x.arr[i]+=y.arr[i]+p;
        p=x.arr[i]/10;
        x.arr[i]%=10;
        x.len=max(x.len,MAXN-i);
    }
    return x;
} //一些高精模板

void input(){
    cin>>n;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            cin>>val[i][j]; 
}

void init(){
    for (int i=0;i<MAXN+10;i++)
        for (int j=0;j<MAXN+10;j++)
            f[i][j]=new_number(); //初始化
}

void DP(){
    f[1][1].arr[MAXN-1]=1;
    f[1][1].len=1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (val[i][j]){ //特判val[i][j]=0的情况
                f[i+val[i][j]][j]=number_add(f[i][j],f[i+val[i][j]][j]);
                f[i][j+val[i][j]]=number_add(f[i][j],f[i][j+val[i][j]]);
            }
}

void output(){
    /*for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++){
            printf("f[%d][%d] = \n",i,j);
            print(f[i][j]);
        }*/
    print(f[n][n]);
}

int main(){
    input();
    init();
    DP();
    output();
    return 0; //好习惯
}