[P1373]小a和uim之大逃离 (DP)

[题目链接]

模拟赛的时候的一道题

因为老师不小心把数据发下来了……我考试打表的

考完之后Orz xzjds

然后开始打正解

题意

大概就是两个人，走矩阵，两个人各加上走上的矩阵的数值，要求最终两个人和相同的方案数有多少

分析

很明显是一个动态规划题

f[i][j][k][a]表示走到(i,j)的时候，值为k，a==1/0 表示第一个人活着第二个人的时候的可能存在的方案数

因为要求的是全部方案数，并且是任意点开始，任意点结束的，所以需要把全部的加起来

（方程式调了很久最后才发现给的k为了方便处理+1比较好在xzjds的思路下做出来的）

代码

#include<bits/stdc++.h>

#define mod 1000000007

#define ll long long

using namespace std;

inline int read() {

    int f = , x = ; char ch;

    do { ch = getchar(); if (ch == '-')f = -; } while (ch<'' || ch>'');

    do { x = x *  + ch - ''; ch = getchar(); } while (ch >= ''&&ch <= '');

    return f * x;

}

int a[][];

int f[][][][];

int main()

{

    int n=read(),m=read(),kk=read();

    kk++;

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=m;j++)

        {

            a[i][j]=read()%mod;

            f[i][j][a[i][j]][]=;

        }

    }

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=m;j++)

        {

            for(int k=;k<=kk-;k++)

            {

                f[i][j+][(k+a[i][j+])%kk][]=(f[i][j+][(k+a[i][j+])%kk][]+f[i][j][k][])%mod;

                f[i+][j][(k+a[i+][j])%kk][]=(f[i+][j][(k+a[i+][j])%kk][]+f[i][j][k][])%mod;

                f[i][j+][(k-a[i][j+]+kk)%kk][]=(f[i][j+][(k-a[i][j+]+kk)%kk][]+f[i][j][k][])%mod;

                f[i+][j][(k-a[i+][j]+kk)%kk][]=(f[i+][j][(k-a[i+][j]+kk)%kk][]+f[i][j][k][])%mod;

            }

        }

    }

    int ans=;

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

    ans=(ans+f[i][j][][])%mod;

    printf("%d",ans);

    return ;

}

巴特西

[P1373]小a和uim之大逃离 (DP)

[题目链接]

题意

分析

代码

最新文章

热门文章