• 【代码源每日一题Div1】路径计数2「动态规划 记忆化搜索」


    路径计数2

    题目描述:

    n*n的网格,有些格子可以走,有些不可以走,不能走的格子的坐标已经给了出来,问你从(1,1)开始,只能往右或者往下走,到(n,n)有多少种路径的方案

    思路:

    挺有意思的一道题,跟前些日子纳新笔试题的倒数第二题有点点类似,但又不同

    首先一个需要知道的东西是,从(1,1)走到(n,m),每次只能往右或者往下走的方案数应该是C(n-1+m-1, n-1)

    首先一看数据范围n=1e6m=3000,就能想到应该是个m*m的一个dp 差不多

    我们可以考虑dp[i]表示从(1,1)出发到(xi, yi)的障碍物,过程不经过其他障碍物的方案数,则我们可以利用“减法”进行状态的计算,即用C(xi-1+yi-1, xi-1)的总的方案数减去其他障碍物j产生的影响。显然xj<=xi && yj<=yi才会对i产生影响,我们就可以从那些状态转移过来,而障碍物(xj,yj)(xi,yi)产生的影响应该是dp[j]*C(xi-xj+yi-yj, xi-xj)

    由于循环不是很好写,需要排序来确定循环顺序,不如直接记忆化,用到什么搜什么

    组合数的板子抄的ygg的捏

    #include 
    using namespace std;
    
    #define int long long
    #define endl '\n'
    #define inf 0x3f3f3f3f
    #define mod7 1000000007
    #define mod9 998244353
    #define m_p(a,b) make_pair(a, b)
    #define mem(a,b) memset((a),(b),sizeof(a))
    #define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    typedef long long ll;
    typedef pair <int,int> pii;
    
    #define MAX 2000000 + 50
    int n, m, k, x;
    struct ran{
        int x, y;
    }tr[MAX];
    
    namespace CNM {
        const int N = 2e6 + 5;
        ll mod = 1e9+7;
        ll quick(ll x, ll n)
        {
            ll res = 1;
            while (n)
            {
                if (n & 1) res = (res*x) % mod;
                x = x * x%mod;
                n >>= 1;
            }
            return res;
        }
        ll inv(ll x) { return quick(x, mod - 2); }
        ll fac[N], invfac[N];
        void init()
        {
            fac[0] = 1;
            for (int i = 1; i < N; ++i) fac[i] = (fac[i - 1] * i) % mod;
            invfac[N - 1] = inv(fac[N - 1]);
            for (int i = N - 2; i >= 0; --i) invfac[i] = (invfac[i + 1] * (i + 1)) % mod;
        }
        ll C(int n, int m)
        {
            if (n < m || m < 0) return 0;
            return fac[n] * invfac[m] % mod*invfac[n - m] % mod;
        }
    }
    
    ll dp[MAX];
    bool vis[MAX];
    ll dfs(int i){
        if(vis[i])return dp[i];
        vis[i] = 1;
        ll ans = 0;
        for(int j = 1; j <= m; ++j){
            if(i == j)continue;
            if(tr[j].x <= tr[i].x && tr[j].y <= tr[i].y){
                (ans += (dfs(j) * CNM::C(tr[i].x-tr[j].x+tr[i].y-tr[j].y, tr[i].x-tr[j].x)%mod7)%mod7)%=mod7;
            }
        }
        dp[i] = ((CNM::C(tr[i].x+tr[i].y-2, tr[i].x-1) - ans)%mod7 + mod7)%mod7;
        return  dp[i];
    }
    
    void work(){
        CNM::init();
        cin >> n >> m;
        for(int i = 1; i <= m; ++i){
            cin >> tr[i].x >> tr[i].y;
        }
        tr[++m].x = n;tr[m].y = n;
        dfs(m);
        cout << dp[m] << endl;
    }
    
    
    signed main(){
        io;
        work();
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
  • 相关阅读:
    【附源码】计算机毕业设计JAVA住房公积金筹集子系统的网站系统
    SpringBoot的@GetMapping路径匹配规则、国际化
    DQL命令查询数据(一)
    【项目】在线oj
    吴恩达深度学习笔记(四)——深度学习的实践层面
    CSDN 成为开放原子开源基金会黄金捐赠人,共建中国十万亿技术大生态
    sparksql的SQL风格编程
    前端在项目中添加自己的功能页面
    聊聊Spring事务控制策略以及@Transactional失效问题避坑
    百度上线“文心一言”付费版本,AI聊天机器人市场竞争加剧
  • 原文地址:https://blog.csdn.net/weixin_51216553/article/details/127780784