题解 | #[NOIP2000]方格取数#

思路:将两个人想象为同时走,这样每个状态 i1+j1==i2+j2==k 且可以布满棋盘,因为由k可以推出j1,j2,即每一步的具***置,故状态为f(k,i1,i2) (注:f[k][i1][i2]表示两人经过同样步数,甲在arr[i1]j1, 乙在arr[i2]j2位置时取数的最大值)

下面分析状态的转移计算,有四种情况: 如果到这个步数甲乙没有重合: f(i1,j1,i2,j2)=f(i1-1,j1,i2-1,j2)+arr[i1][j1]+arr[i2][j2] //对应甲从左边来,乙从左边来,下面同理可推 f(i1,j1,i2,j2)=f(i1-1,j1,i2,j2-1)+arr[i1][j1]+arr[i2][j2] f(i1,j1,i2,j2)=f(i1,j1-1,i2-1,j2)+arr[i1][j1]+arr[i2][j2] f(i1,j1,i2,j2)=f(i1,j1-1,i2,j2-1)+arr[i1][j1]+arr[i2][j2] 如果到这个步数甲乙重合: f(i1,j1,i2,j2)=f(i1-1,j1,i2-1,j2)+arr[i1][j1] //甲取走数,该位置的数变为0,对应甲从左边来,乙从左边来,下面同理可推 f(i1,j1,i2,j2)=f(i1-1,j1,i2,j2-1)+arr[i1][j1] f(i1,j1,i2,j2)=f(i1,j1-1,i2-1,j2)+arr[i1][j1] f(i1,j1,i2,j2)=f(i1,j1-1,i2,j2-1)+arr[i1][j1]

优化为3维就是 f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2 - 1] + t); f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2] + t); f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2 - 1] + t); f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2] + t);//因为k=i1+j1=i2+j2. i1,i2不变, k-1时, 则对应j1-1, j2-1

最终ac代码如下： #include #include #include

using namespace std;

const int N=15; int arr[N][N]; int f[N + N][N][N];

//将两个人想象为同时走,这样每个状态 i1+j1==i2+j2==k 且可以布满棋盘,因为由k可以推出j1,j2,即每一步的具***置,故状态为f(k,i1,i2) int main() { int r; cin >> r;

int a, b, c;
while (cin >> a >> b >> c&&a || b || c)
{
	arr[a][b] = c;
}
for(int k=2;k<=2*r;k++)
	for(int i1=1;i1<=r;i1++)
		for (int i2 = 1; i2 <= r; i2++)
		{
			int j1 = k - i1, j2 = k - i2;
			if (j1>=1&&j1<=r&&j2>=1&&j2<=r)//注意判断条件
			{
				int t = arr[i1][k - i1];
				if (i1 != i2)t += arr[i2][k - i2];//注意加的逻辑,如果不重合 arr[i1][j1]可能不等于arr[i2][j2],需要加上两个
				f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2] + t);
				f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2 - 1] + t);
				f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2 - 1] + t);
				f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2] + t);
			}
			
		}
cout << f[r+r][r][r] << endl;

}