[题目链接]
模拟赛的时候的一道题
因为老师不小心把数据发下来了……我考试打表的
考完之后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 =
1, x =
0;
char ch;
do { ch = getchar();
if (ch ==
'-')f = -
1; }
while (ch<
'0' || ch>
'9');
do { x = x *
10 + ch -
'0'; ch = getchar(); }
while (ch >=
'0'&&ch <=
'9');
return f *
x;
}
int a[
805][
805];
int f[
805][
805][
20][
2];
int main()
{
int n=read(),m=read(),kk=
read();
kk++
;
for(
int i=
1;i<=n;i++
)
{
for(
int j=
1;j<=m;j++
)
{
a[i][j]=read()%
mod;
f[i][j][a[i][j]][0]=
1;
}
}
for(
int i=
1;i<=n;i++
)
{
for(
int j=
1;j<=m;j++
)
{
for(
int k=
0;k<=kk-
1;k++
)
{
f[i][j+
1][(k+a[i][j+
1])%kk][
0]=(f[i][j+
1][(k+a[i][j+
1])%kk][
0]+f[i][j][k][
1])%
mod;
f[i+
1][j][(k+a[i+
1][j])%kk][
0]=(f[i+
1][j][(k+a[i+
1][j])%kk][
0]+f[i][j][k][
1])%
mod;
f[i][j+
1][(k-a[i][j+
1]+kk)%kk][
1]=(f[i][j+
1][(k-a[i][j+
1]+kk)%kk][
1]+f[i][j][k][
0])%
mod;
f[i+
1][j][(k-a[i+
1][j]+kk)%kk][
1]=(f[i+
1][j][(k-a[i+
1][j]+kk)%kk][
1]+f[i][j][k][
0])%
mod;
}
}
}
int ans=
0;
for(
int i=
1;i<=n;i++
)
for(
int j=
1;j<=m;j++
)
ans=(ans+f[i][j][
0][
1])%
mod;
printf("%d",ans);
return 0;
}
转载于:https://www.cnblogs.com/lincold/p/9844738.html
