洛谷 P1373 小a和uim之大逃离

2016-05-30 12:31:59

题目链接: P1373 小a和uim之大逃离

题目大意:

  一个N*M的带权矩阵,以任意起点开始向右或者向下走,使得奇数步所得权值和与偶数步所得权值和关于K的余数都为0,并且要求奇数步等于偶数步

解法:

  动态规划

  DP[i][j][k][now];

  表示当前节点为(i,j),小A比uim多K,当前该now继续走的方案总数

  状态转移方程

    DP[i][j][k][1]=DP[i-1][j][(k+map[i][j])%(K+1)][0]+DP[i][j-1][(k+map[i][j])%(K+1)][0];

    DP[i][j][k][0]=DP[i-1][j][(k-map[i][j]+K+1)%(K+1)][1]+DP[i][j-1][(k-map[i][j]+K+1)%(K+1)][1];

    K表示瓶子的最大容量,所以要+1

    map[i][j]表示(i,j)的权值

    初始条件 DP[i][j][map[i][j]][0]=1;

需要注意的地方:

  注意是N和M,五十分调了半天就因为M写成了N

//小a和uim之大逃离 (洛谷 No.1373)
//动态规划
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=;
const int maxm=;
const int maxk=;
const int MOD=;
int map[maxn][maxm];
int DP[maxn][maxm][maxk][];
int N,M,K;
int ans;
int main()
{
scanf("%d %d %d",&N,&M,&K);
K++;
for(int i=;i<=N;i++)
{
for(int j=;j<=M;j++)
{
scanf("%d",&map[i][j]);
DP[i][j][map[i][j]][]=;
}
}
for(int i=;i<=N;i++)
{
for(int j=;j<=M;j++)
{
for(int k=;k<K;k++)
{
DP[i][j][k][]+=DP[i-][j][(k-map[i][j]+K)%K][];
DP[i][j][k][]+=DP[i][j-][(k-map[i][j]+K)%K][];
DP[i][j][k][]+=DP[i-][j][(k+map[i][j])%K][];
DP[i][j][k][]+=DP[i][j-][(k+map[i][j])%K][];
DP[i][j][k][]%=MOD;
DP[i][j][k][]%=MOD;
}
ans=(ans+DP[i][j][][]%MOD)%MOD;
}
}
printf("%d",ans);
}
上一篇:strus2 action重复执行问题


下一篇:z-index优先级总结