【CSP2020PJ T4】方格取數 題解（記憶化搜索）

【題目描述】
設有 𝑛 × 𝑚 的方格圖，每個方格中都有一個整數，現有一只小熊，想從圖的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重復經過已經走過的方格，也不能走出邊界，小熊會取走所有經過的方格中的整數，
求它能取到的整數之和的最大值，

【分析問題】
考場上看到這個標題，一愣，再一看這個題：
！！！！！
這不就是一道經典dp嗎
于是開心地敲了半天代碼，寫到回圈，發現…
這題居然還可以往上走！！！
這個時候我就暈了，果斷先寫個dfs，再考慮記憶化
（然后寫了半天，有思路了，結果考試結束QAQ）

emmmm，瞎扯得有點多了
首先，這個題不是傳統的方格取數，所以要做一些改變
設記憶化陣列f[i][j]表示從（1,1）走到（i，j）取到的最大值
我們在記憶化陣列里面再加一維，讓它變成f[1001][1001][3]，定義如下：
設是f(i , j , k)是從（x，y）走到（i，j）得到的最大值
k = 0:i = x + 1,j = y
k = 1:i = x,j = y + 1
k = 2:i = x - 1,j = y
你可能有些疑惑，這些東西有什么用？
用處很大！！！
有了這個東西，我們就能得出上一格(x,y)的坐標，再列舉記憶化陣列f(x , y)的第三維下標k
這里注意一個細節，如果當前f(i , j , k)中k = 0或2
那么f(x , y , k)中k != 2或0
換句話說，f(i , j , k)中，k = 0，那么f(x , y , k)中，k = 0或1；
k = 2時同理

不難理解，如果f(i , j , k)中k = 0，那么(i , j)就是由(i - 1,j)得來的，此時如果k = 2，也就是i - 1再+1，那就回來了，死回圈

這樣我們就解決了不能重復的問題~~
（注意，記憶化一定要寫對啊，考場上nt了沒寫對QAQ）
【代碼】

#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF -0x3f3f3f3f
using namespace std;
const int maxn = 1005;
typedef long long LL;
LL f[maxn][maxn][3]; //極端情況可能會爆int      
int a[maxn][maxn];                 
bool vis[maxn][maxn];
int n,m; 
inline bool judge(int x,int y) {
	return x >= 1&&x <= n&&y >= 1&&y <= m;//判斷邊界 
}    
//上一格(x , y) 
//0:由上一格x-1得來             
//1：由上一格y+1得來
//2：由上一格x+1得來                                   
inline LL dfs(int x,int y,int k) {
	LL& ans = f[x][y][k];        
	if(ans != INF) {                           
		return ans;      //就是這里，寫反了，結果調了好久沒調出來QAQ                                         
	}            //這里我的代碼和博客里有點不一樣
	//博客里我寫的是當前點(i,j),考場上我寫的是當前點(x,y)QAQ 
	vis[x][y] = true;
	int i,j;                                                                                                           
	if(k == 0) {                  
		i = x + 1;//反推出上一格坐標 
		j = y;                                                                                                   
		if(judge(i , j)&&!vis[i][j]) {//列舉 
			ans = max(ans , max(dfs(i , j , 1) + (LL)a[x][y] , dfs(i , j , 0) + (LL)a[x][y]));
		}                      
	}
	if(k == 1) {
		i = x;                                     
		j = y - 1;    
		if(judge(i , j)&&!vis[i][j]) {//這里，當k = 1時就沒有任何限制，三種情況都可 
			ans = max(ans , max(dfs(i , j , 0) + (LL)a[x][y] , max(dfs(i , j , 1) + (LL)a[x][y] , dfs(i , j , 2) + (LL)a[x][y])));
		}                        
	}               
	if(k == 2) {     
		i = x - 1;
		j = y;                                                                                        
		if(judge(i , j)&&!vis[i][j]) {               
			ans = max(ans , max(dfs(i , j , 1) + (LL)a[x][y] , dfs(i , j , 2) + (LL)a[x][y]));
		}                                                              
	}                                                                                                                         
	vis[x][y] = false;                                                                                          
	return ans;
}                                                   
int main() {               
	freopen("number.in","r",stdin);                
	freopen("number.out","w",stdout);
	scanf("%d%d",&n,&m);                            
	for(int i = 1;i <= n;++ i) {
		for(int j = 1;j <= m;++ j) {     
			scanf("%d",&a[i][j]);   
			f[i][j][0] = f[i][j][1] = f[i][j][2] = INF;//記憶化初始化 
		}    
	}                                                              
	f[1][1][0] = f[1][1][1] = f[1][1][2] = a[1][1];//起點初始化QAQ 
	printf("%lld",max(dfs(n , m , 1) , dfs(n , m , 2)));//這里，由于n已經在最底層，不可能從下面走上來，所以不寫k = 0 
	fclose(stdin);                
	fclose(stdout);
	return 0;
}

【感想】
這次CSP讓我認識到了很多不足之處，比如對于時間的掌控
好好學習，調整心態，明年再戰！！！！