海洋之心


私信TA

用户名:wanggongsheng

访问量:122486

签 名:

等  级
排  名 17
经  验 20491
参赛次数 3
文章发表 163
年  龄 26
在职情况 学生
学  校
专  业 计算机技术

  自我简介:

读研ing,平时不登录dotcpp

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int g[100][100];
int d[100][100][50][50];
int n,m,k;
int dp(int x,int y,int num,int big){
	if(d[x][y][num][big]!=-1) return d[x][y][num][big];
	d[x][y][num][big]=0;
	if(x==n&&y==m&&k==num) d[x][y][num][big]=1;
	if(g[x][y]>big&&k>num)
	{
		d[x][y][num][big]+=dp(x,y,num+1,g[x][y]);
		d[x][y][num][big]%=1000000007;
	}
	if(x<n)
	{
		d[x][y][num][big]+=dp(x+1,y,num,big);
		d[x][y][num][big]%=1000000007;
	} 
	if(y<m)
	{
		d[x][y][num][big]+=dp(x,y+1,num,big);
		d[x][y][num][big]%=1000000007;
	}
	return d[x][y][num][big];
}
int main(void){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++){
		cin>>g[i][j];
		g[i][j]++;
	}	
	memset(d,-1,sizeof(d));
	dp(1,1,0,0);
	cout<<d[1][1][0][0]<<endl;
	return 0;
}

使用了记忆化搜索的方式,但是一开始出现了超时的问题,出现超时间限制的情况如下代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int g[100][100];
int d[100][100][50][50];
int n,m,k;
int dp(int x,int y,int num,int big){
	if(d[x][y][num][big]) return d[x][y][num][big];
	d[x][y][num][big]=0;
	if(x==n&&y==m&&k==num) d[x][y][num][big]=1;
	if(g[x][y]>big&&k>num)
	{
		d[x][y][num][big]+=dp(x,y,num+1,g[x][y]);
		d[x][y][num][big]%=1000000007;
	}
	if(x<n)
	{
		d[x][y][num][big]+=dp(x+1,y,num,big);
		d[x][y][num][big]%=1000000007;
	} 
	if(y<m)
	{
		d[x][y][num][big]+=dp(x,y+1,num,big);
		d[x][y][num][big]%=1000000007;
	}
	return d[x][y][num][big];
}
int main(void){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++){
		cin>>g[i][j];
		g[i][j]++;
	}	
	dp(1,1,0,0);
	cout<<d[1][1][0][0]<<endl;
	return 0;
}

原因是没有使用好记忆化搜索的优势,导致了方法的退化,出现了重复计算的现象

最好的解决方式是

使用一个数组来进行保存是否进行了访问,防止了出错,采用了用空间开换时间的策略

vis[][][][]

没有给出具体的代码,自己实现

 

0.0分

3 人评分

  评论区

大佬g[i][j]++,是啥意识呢?
2019-03-05 17:17:53
  • «
  • 1
  • »