黑妹的游戏II

第一行一个整数T表示数据的组数。(1 ≤ T ≤ 20)
对于每组数据：
第一行两个整数n，m表示棋盘的规格。(1 ≤ n, m ≤ 500)
接下来n行每行m个整数aij表示方格对应的分数。( $0 \le a_{ij} \le 10000$ )

C++14(g++5.4) 解法, 执行用时: 537ms, 内存消耗: 1508K, 提交时间: 2018-06-29 19:36:58

#include<bits/stdc++.h>
using namespace std;
int a[510][510];
int main(){
	int T,n,m;
	cin>>T;
	for(int t=1;t<=T;t++){
		memset(a,0,sizeof(a));
		cin>>n>>m;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				scanf("%d",a[i]+j);
		for(int i=n;i>=1;i--)
			for(int j=m;j>=1;j--){
				if(j+1<=m){
					if(i+1<=n)a[i][j]=min(a[i][j]-a[i+1][j],a[i][j]-a[i][j+1]);
					else a[i][j]=a[i][j]-a[i][j+1];
				}
				else if(i+1<=n)a[i][j]=a[i][j]-a[i+1][j];
			}
		cout<<a[1][1]<<endl;
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 644ms, 内存消耗: 1520K, 提交时间: 2020-04-03 20:25:10

#include<iostream>
using namespace std;
int t,n,m;
int amap[505][505];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d",&n,&m);
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		scanf("%d",&amap[i][j]);
		for(int i=n;i>=1;--i)
		for(int j=m;j>=1;--j)
		if(i!=n&&j!=m) amap[i][j]-=max(amap[i+1][j],amap[i][j+1]);
		else if(i!=n&&j==m) amap[i][j]-=amap[i+1][j];
		else if(j!=m&&i==n) amap[i][j]-=amap[i][j+1];
		printf("%d\n",amap[1][1]);
	}
}

详情