60分 wa3 4求助
查看原帖
60分 wa3 4求助
277023
YuanZhizheng楼主2020/8/16 19:53
#include<bits/stdc++.h>
using namespace std;
#define rep(i,k,n) for(long long i=k;i<=n;i++)
#define per(i,n,k) for(long long i=n;i>=k;i--)
#define pb push_back
#define fi first
#define se second
#pragma GCC optimize(3,"Ofast","inline")
typedef long long ll;
typedef double db;
typedef long double ldb;
//typedef pair<ll,ll> P;
const ll mod=1e9+7;
ll gcd(ll a,ll b)
{
    ll r;
    while(b>0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
ll read()
{
    ll x=0;
    char f=1,c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
ll fp(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
ll lcm(ll a,ll b)
{
    return a/gcd(a,b)*b;
}
int cmp(ll a,ll b)
{
    return a>b;
}
ll dp[25][25];
bool vis[25][25];
int main()
{
    int n=read(),m=read();
    int x=read(),y=read();
    rep(i,0,24)///初始化行列为1
    {
        dp[i][0]=1LL;
        dp[0][i]=1LL;
    }

    rep(i,0, n)
    {
        rep(j,0,m)
        {
            if(abs(i-x)+abs(j-y)==3&&i!=x&&j!=y)///标记控制点
                vis[i][j]=1,dp[i][j]=0;
        }
    }
    vis[x][y]=1;
    dp[x][y]=0;

    rep(i,1,n)///递推,0行0列不用推
    {
        rep(j,1,m)
        {
            if(vis[i][j])continue;
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
    }
    printf("%lld\n",dp[n][m]);
    return 0;
}
2020/8/16 19:53
加载中...