专栏文章

题解：P1004 [NOIP2000 提高组] 方格取数

许许卿安
P1004题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqenmtx
此快照首次捕获于
2025/12/04 03:33
3 个月前
此快照最后确认于
2025/12/04 03:33
3 个月前
查看原文
经典动态规划题目，本篇题解使用的是三维 dp。
由于要走两遍，所以我们直接处理两条路径。设 dpi1,j1,i2,j2dp_{i_1,j_1,i_2,j_2} 表示走了 i1+j1i_1+j_1 步，第一条路径走到 (i1,j1)(i_1,j_1)，第二条路径走到 (i2,j2)(i_2,j_2) 的最大取数之和。显然有 i1+j1=i2+j2i_1+j_1=i_2+j_2，因此 j2j_2 一维可以压掉。
如果两条路径走到同一格，那么当前格子只能加一次。有状态转移方程 dpi1,j1,i2={sci1,j1+max⁡(dpi1,j1−1,i2−1,dpi1−1,j1,i2)i1=i2sci1,j1+sci2,i1+j1−i2+max⁡(dpi1−1,j1,i2−1,dpi1−1,j1,i2,dpi1,j1−1,i2−1,dpi1,j1−1,i2)i1≠i2dp_{i_1,j_1,i_2}=\begin{cases}sc_{i_1,j_1}+\max(dp_{i_1,j_1-1,i_2-1},dp_{i_1-1,j_1,i_2}) & i_1=i_2\\sc_{i_1,j_1}+sc_{i_2,i_1+j_1-i_2}+\max(dp_{i_1-1,j_1,i_2-1},dp_{i_1-1,j_1,i_2},dp_{i_1,j_1-1,i_2-1},dp_{i_1,j_1-1,i_2}) & i_1\ne i_2\end{cases}。
其中 sci,jsc_{i,j} 表示 (i,j)(i,j) 格上的数。
CPP
#include<bits/stdc++.h>
using namespace std;

const int N=12;
int sc[N][N];
int dp[N][N][N]; 

int main(){
	int n;cin>>n;int x,y,z;
	while(cin>>x>>y>>z){
		if(!(x || y || z)) break;
		sc[x][y]=z;
	}
	for(int i1=1; i1<=n; i1++){
		for(int j1=1; j1<=n; j1++){
			for(int i2=1; i2<=i1+j1-1; i2++){
				if(i1==i2) dp[i1][j1][i2]=sc[i1][j1]+max(dp[i1][j1-1][i2-1],dp[i1-1][j1][i2]);
				else dp[i1][j1][i2]=sc[i1][j1]+sc[i2][i1+j1-i2]+max({dp[i1-1][j1][i2-1],dp[i1-1][j1][i2],dp[i1][j1-1][i2-1],dp[i1][j1-1][i2]});
//				cout<<i1<<" "<<j1<<" "<<i2<<" "<<dp[i1][j1][i2]<<"\n";
			}
//			cout<<"\n";
		}
	}
	cout<<dp[n][n][n];
	return 0;
}
因为两条路径长度相同，所以第二条路径一定不会走到第一条路径曾经过的点。所以是否将第一条路径上经过的点上的数赋零对答案无影响。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...