luogu-P7074-方格取數2020

題目連接配接

• 該題是CSP-J2-2020-T4

題目大意

在一個棋盤内，允許向右，或者向上、下移動，求經過的點的和最大。

題目分析

1、顯然是DP題，但是和之前的方格取數（4維降3維）有一丁點差別；

2、如果對于每個點，都從三個方向過來，需要 O ( n 3 ) O(n^3) O(n3) ，能得 70 70 70 分；

3、如果分開數組做，用 d n [ i ] [ j ] dn[i][j] dn[i][j] 表示從上往下的最值， u p [ i ] [ j ] up[i][j] up[i][j] 表從下往上的最值， f [ i ] [ j ] f[i][j] f[i][j] 表示從左往右的最值，則可以在 O ( n 2 ) O(n^2) O(n2) 解答。

參考代碼

//T4-方格取數 
//CSP-J2-2020
//三個方向的DP 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=1e18+9;
const int maxn=1e3+9;
int n,m;
ll a[maxn][maxn],up[maxn][maxn],dn[maxn][maxn],f[maxn][maxn];

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%lld",&a[i][j]);
		}
	}
	//初始化 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			f[i][j]=up[i][j]=dn[i][j]=-inf;
		}
	}
	f[1][1]=a[1][1];
	
	for(int i=2;i<=n;i++) f[i][1]=f[i-1][1]+a[i][1];
	for(int j=2;j<=m;j++){
		dn[1][j]=f[1][j-1]+a[1][j];
		for(int i=2;  i<=n;i++) dn[i][j]=max(f[i][j-1],dn[i-1][j])+a[i][j];
		up[n][j]=f[n][j-1]+a[n][j];
		for(int i=n-1;i>=1;i--) up[i][j]=max(f[i][j-1],up[i+1][j])+a[i][j];
		for(int i=1;i<=n;i++) f[i][j]=max(dn[i][j],up[i][j]);
	} 
	cout<<f[n][m];
	
	return 0;
} 

           

one more thing

• 感謝馬子衡同學詳細的分析
• 20 20 20分

爆搜，時間複雜度為 O ( ? ) O(?) O(?)；

• 70 70 70分

考慮 d p dp dp。令 d p i , j dp_{i,j} dpi,j​為來到這個點的最大的取到的整數和。

我們意識到我們不可能從右往左，是以我們的 d p dp dp 一定是從左向右的枚舉的。考慮一個點 ( i , j ) (i,j) (i,j)，這一個點可以從 ( i , j − 1 ) (i,j-1) (i,j−1)轉移而來，也有可能是從 ( k , j )   ( k ∈ [ 1 , n ] , k ≠ i ) (k,j)\ (k\in[1,n],k \ne i) (k,j) (k∈[1,n],k​=i)轉移而來的。很容易想到轉移方程：

d p i , j = max ⁡ k = 0 k ≤ n { d p k , j − 1 + d i s k , i , j } ， 其 中 d i s k , i , j 表 示 從 ( k , j ) 走 到 ( i , j ) 所 取 的 和 dp_{i,j} = \max\limits_{k=0}^{k\le n}\{dp_{k,j-1}+dis_{k,i,j}\}，其中dis_{k,i,j}表示從(k,j)走到(i,j)所取的和 dpi,j​=k=0maxk≤n​{dpk,j−1​+disk,i,j​}，其中disk,i,j​表示從(k,j)走到(i,j)所取的和

很容易 O ( n 3 ) O(n^3) O(n3)轉移

• 100 100 100分

考慮優化剛才的思路。我們令 u p i , j up_{i,j} upi,j​表示從下往上走到 ( i , j ) (i,j) (i,j)所得到的最大和， d n i , j dn_{i,j} dni,j​表示從上往下走到 ( i , j ) (i,j) (i,j)所得到的最大和。

我們發現，若對于 ( i , j ) (i,j) (i,j)而言，其 u p i , j up_{i,j} upi,j​的方案的來源為 ( k , j ) (k,j) (k,j)，那麼，對于 x ∈ [ i , k ] x\in[i,k] x∈[i,k]的 ( x , j ) (x,j) (x,j)的所有方案都将會是從 ( k , j ) (k,j) (k,j)轉移而來的。是以說我們隻依賴與 ( i + 1 , j ) (i+1,j) (i+1,j)的狀态來擷取 u p i , j up_{i,j} upi,j​，這樣就可以 O ( 1 ) O(1) O(1)求得 u p up up了。對于 d n dn dn同理。

于是，我們可以更改剛才的轉移方程為：

時間複雜度為 O ( n 2 ) O(n^2) O(n2)