题解：B4140 [信息与未来 2016] 方格取数

这道题数据量很大，我们一条一条梳理。

方格

注意到这道题方格里的数需要自己算出来，所以我们按照题目中的代码写一下就好了，问题应该不是很大。

CPP

for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			s=(s*345)%19997;
			a[i][j]=(s%10)+1;
		}
	}

搜索

这题的算法就是搜索，但是用记忆化搜索可以不重不漏的搜，然后里面可能参杂着一点动态规划的元素吧。

然后怎么搜就是文章的重点了。

首先，我们判断这个点我们是不是已经找到了，如果是，我们就直接返回，否则就继续。

然后我们枚举上下左右四个方向，我们可以用两个数组来表示四个方向。然后呢，判断四个方向是否都是成立的。如果成立，就判断这个点原来的数是不是比四个方向的数大，如果大就交换。

我们再来讲判断条件。判断条件就简单了。首先看这个点是不是在方格里面，然后判断这个点的元素是不是比我们要算的点的元素要大。如果都满足，比较就行了。如何比较请看上一段。

CPP

long long dx[4]={-1, 1, 0, 0}, dy[4]={0, 0, -1, 1};
long long f(int x, int y) {
    if(dp[x][y]) return dp[x][y];
    dp[x][y]=a[x][y];
    for(int i=0;i<4;i++){
        int nx=x+dx[i], ny=y+dy[i];
        if (nx>=1 && nx<=n && ny>=1 && ny<=m && a[nx][ny]>a[x][y]){
            dp[x][y]=max(dp[x][y], f(nx, ny)+a[x][y]);
        }
    }
    return dp[x][y];
}

答案

注意哈，题目没有固定起点和终点，所以我们就不能直接输出。而是找方格里面的最大值输出。

CPP

for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)	
			ans=max(ans,f(i,j));

代码

把代码拼一拼就好了，注释放在下面了。

CPP

#include<bits/stdc++.h>//万能头文件
using namespace std;
long long n, m, s;
long long a[1010][1010];
long long dp[1010][1010];//每个点的答案
long long dx[4]={-1, 1, 0, 0}, dy[4]={0, 0, -1, 1};//四个方向
long long ans;//最终答案
long long f(int x, int y) {
    if(dp[x][y]) return dp[x][y];//如果早就找到了，那就直接返回这个答案
    dp[x][y]=a[x][y];//把这个点的答案先初始化成这个点的数
    for(int i=0;i<4;i++){//枚举四个方向
        int nx=x+dx[i], ny=y+dy[i];//坐标
        if (nx>=1 && nx<=n && ny>=1 && ny<=m && a[nx][ny]>a[x][y]){//如果成立
            dp[x][y]=max(dp[x][y], f(nx, ny)+a[x][y]);//看我从哪个方向过来最划算
        }
    }
    return dp[x][y];//返回这个点的答案
}
int main(){
    cin>>n>>m>>s;//输入答案
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			s=(s*345)%19997;//构造方格里面的数
			a[i][j]=(s%10)+1;
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)	
			ans=max(ans,f(i,j));//寻找答案
	cout<<ans<<endl;//输出答案
    return 0;//结束程序
}

题解：B4140 [信息与未来 2016] 方格取数

文章操作

方格

搜索

答案

代码

相关推荐

评论

题解：B4140 [信息与未来 2016] 方格取数