题解：SP16212 DCEPC11J - Jailbreak

helongyun · 2024-12-11 17:32:47 · 题解

题目传送门

题目描述

这是一道动态规划。

题目思路

要知道到达 f_{i,j} 有几种方法，实际上就是求 f_{i-1,j}+f_{i-2,j}\times2+f_{i,j-1}+f_{i,j-2}\times2 的和，再优化一下，虽然有多组数据，但是都可以用一个图来表示，所以先算出图各个位置的值，最后输入时直接输出。

注意

记得取模。

code

#include<bits/stdc++.h>
using namespace std;
int t,n,m,f[10005][10005];
long long mod=1e9+7;
int main()
{
    cin>>t;
    f[1][1]=1;
    for(int j=1;j<=505;j++)
    {
        for(int k=1;k<=505;k++)
        {
            if(j==1&&k==1) continue;
            if(j>=1) f[j][k]=(f[j][k]+f[j-1][k])%mod;
            if(j>=2) f[j][k]=(f[j][k]+f[j-2][k]*2)%mod;
            if(k>=2) f[j][k]=(f[j][k]+f[j][k-2]*2)%mod;
            if(k>=1) f[j][k]=(f[j][k]+f[j][k-1])%mod;
            f[j][k]%=mod;
        }
    }//先算出各个位置的值
    for(int i=1;i<=t;i++)
    {
        cin>>n>>m;
        cout<<f[n][m]<<endl;
    }//输出
}