每日一题 day30 打卡

Analysis

f[i][j][p][q]表示他们走到(i,j),且两人魔瓶内魔液量的差为p时的方法数。q=0表示最后一步是小a走的,q=1表示最后一步是uim走的。题目中说魔瓶的容量为k,实际上就是动归时p需要对k+1取余数,即p只有0~k,k+1种可能。答案为所有f[i][j][0][1]的和。

动归方程如下:(为了方便已经令k=k+1)

f[i][j][p][0]+=f[i-1][j][(p-mapp[i][j]+k)%k][1] (i-1>=1)

f[i][j][p][0]+=f[i][j-1][(p-mapp[i][j]+k)%k][1] (j-1>=1)

f[i][j][p][1]+=f[i-1][j][(p+mapp[i][j])%k][0] (i-1>=1)

f[i][j][p][1]+=f[i][j-1][(p+mapp[i][j])%k][0] (j-1>=1)

还有每个格子都有可能作为小a的起始格子,所以初始时对于所有i、j,f[i][j][mapp[i][j]][0]=1。

算法复杂度o(n*m*k)

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 800+10
#define mod 1000000007
using namespace std;
inline int read()
{
int x=;
bool f=;
char c=getchar();
for(; !isdigit(c); c=getchar()) if(c=='-') f=;
for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';
if(f) return x;
return -x;
}
inline void write(long long x)
{
if(x<){putchar('-');x=-x;}
if(x>)write(x/);
putchar(x%+'');
}
int n,m,k;
int map[maxn][maxn];
int dp[maxn][maxn][][];
int main()
{
n=read();m=read();k=read();
k++;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
map[i][j]=read();
dp[i][j][map[i][j]][]=;
}
long long ans=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
for(int p=;p<=k;p++)
{
dp[i][j][p][]=(dp[i][j][p][]+dp[i-][j][(p-map[i][j]+k)%k][])%mod;
dp[i][j][p][]=(dp[i][j][p][]+dp[i][j-][(p-map[i][j]+k)%k][])%mod;
dp[i][j][p][]=(dp[i][j][p][]+dp[i-][j][(p+map[i][j])%k][])%mod;
dp[i][j][p][]=(dp[i][j][p][]+dp[i][j-][(p+map[i][j])%k][])%mod;
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
ans=(ans+dp[i][j][][])%mod;
write(ans);
return ;
}

请各位大佬斧正(反正我不认识斧正是什么意思)

最新文章

  1. 【Win10 应用开发】从前台应用触发后台任务
  2. Python“Non-ASCII character &#39;xe5&#39; in file”报错问题(转)
  3. 编写jquery常用插件的基本格式
  4. SQL疑难杂症【4 】大量数据查询的时候避免子查询
  5. 使用Eclipse自带Web Service插件(Axis1.4)生成Web Service服务端/客户端
  6. java io读书笔记(3)数值类型的数据
  7. source insight用于C语言编程的工具脚本
  8. java web-----DAO设计模式(数据库访问)
  9. poj 3692 Kindergarten (最大独立集之逆匹配)
  10. 使用 IObjectSafety 标记 ATL 控件初始化的安全
  11. python学习笔记之一:列表与元组
  12. C#自定义运行时窗体设计器Runtime FormDesigner
  13. 防XXS和SQL注入
  14. 清除被占用的8080端口,否则npm run dev无法正常运行
  15. 【学亮IT手记】Java 8新特性实例介绍
  16. python 处理 https链接 socket报错 链接https
  17. 多目标遗传算法 ------ NSGA-II (部分源码解析)二元锦标赛选择 tourselect.c
  18. spring+springMVC+mybatis+maven+mysql环境搭建(一)
  19. Springboot整合log4j2日志全解
  20. 解决启动Distributed Transaction Coordinator服务出错的问题

热门文章

  1. Javascript获取JSON对象长度
  2. 在Python中创建和使用类
  3. 深度学习-LSTM与GRU
  4. REST framework之分页组件
  5. adb命令查看连接PC的移动设备
  6. golang---获取windows系统相关信息
  7. 普通element ui table组件的使用
  8. Java调用WebService方法总结(8)--soap.jar调用WebService
  9. jenkins配置Webhook-gitlab
  10. 行内块inline-block元素之间出现空白间隙原因及解决办法