51nod1084 矩阵取数问题 V2

O(n4)->O(n3)妈呀为什么跑这么慢woc

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

using namespace std;

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define clr(x,c) memset(x,c,sizeof(x))

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int nmax=205;

int a[nmax][nmax],dp[nmax][nmax][nmax<<1],n,m;

bool check(int x,int y){

	if(x<=0||x>n||y<=0||y>m) return 0;

	return 1;

}

int aa[5]={0,0,0,-1,-1};

int bb[5]={0,-1,-1,0,0};

int cc[5]={0,0,-1,0,-1};

int dd[5]={0,-1,0,-1,0};

void maxs(int &a,int b){

	if(a<b) a=b;

}

int main(){

	m=read(),n=read();

	rep(i,1,n) rep(j,1,m) a[i][j]=read();

	dp[1][1][1]=a[1][1];int ta,tb,u,v,d,o;

	rep(i,2,n+m-1){

		rep(j,1,min(i,n)) rep(k,1,min(i,n)){

			ta=i-j+1,tb=i-k+1;int &ts=dp[j][k][i];

			rep(t,1,4) {

				u=j+aa[t];v=ta+bb[t];d=k+cc[t];o=tb+dd[t];

				if(!check(u,v)||!check(d,o)) continue;

				maxs(ts,dp[u][d][i-1]);

			}

			if(j==k) ts+=a[j][ta];

			else ts+=a[j][ta]+a[k][tb];

		}

	}

	printf("%d\n",dp[n][n][n+m-1]);

	return 0;

}

1084 矩阵取数问题 V2 51nod1084 矩阵取数问题 V2

基准时间限制：2 秒空间限制：131072 KB 分值: 80 难度：5级算法题

关注

一个M*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，先从左上走到右下，再从右下走到左上。第1遍时只能向下和向右走，第2遍时只能向上和向左走。两次如果经过同一个格子，则该格子的奖励只计算一次，求能够获得的最大价值。

例如：3 * 3的方格。

1 3 3

2 1 3

2 2 1

能够获得的最大价值为：17。1 -> 3 -> 3 -> 3 -> 1 -> 2 -> 2 -> 2 -> 1。其中起点和终点的奖励只计算1次。

Input

第1行：2个数M N，中间用空格分隔，为矩阵的大小。(2 <= M, N <= 200)

第2 - N + 1行：每行M个数，中间用空格隔开，对应格子中奖励的价值。(1 <= A[i,j] <= 10000)

Output

输出能够获得的最大价值。

Input示例

Output示例

秒客网

51nod1084 矩阵取数问题 V2

相关文章