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);
}