上午T4 30分求助
  • 板块学术版
  • 楼主duoluoluo
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/9/20 13:37
  • 上次更新2023/11/4 06:05:07
查看原帖
上午T4 30分求助
107640
duoluoluo楼主2021/9/20 13:37
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 310;
int n, m, xs, ys, xk, yk;
long long map[N][N], a[N][N], g[N][N], u[N << 1][N][N], v[N << 1][N][N], ans;
long long Max(long long a,long long b,long long c,long long d)
{
	return (((((a>b)?a:b)>c)?((a>b)?a:b):c)>d)?((((a>b)?a:b)>c)?((a>b)?a:b):c):d;
}
int main () {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++) {
			scanf("%lld", &map[i][j]);
			if (map[i][j] > 0) a[i][j] = map[i][j];
		}
	scanf("%d%d%d%d", &xs, &ys, &xk, &yk);
	for (int i = xk; i >= 1; i --)
		for (int j = yk; j >= 1; j --)
			g[i][j] = map[i][j] + max(g[i][j + 1], g[i + 1][j]);
	for (int i = 1; i <= xs + ys - 1; i ++)
		for (int j = 1; j <= i && j <= xs; j ++)
			for (int k = 1; k <= i && k <= xs; k ++) {
				u[i][j][k] = map[j][i - j + 1] + map[k][i - k + 1] + Max(u[i - 1][j][k], u[i - 1][j - 1][k - 1], u[i - 1][j - 1][k], u[i - 1][j][k - 1]);
				if (j == k) u[i][j][k] -= map[j][i - j + 1];
				v[i][j][k] = map[j][i - j + 1] + a[k][i - k + 1] + Max(v[i - 1][j][k], v[i - 1][j - 1][k - 1], v[i - 1][j - 1][k], v[i - 1][j][k - 1]);
				if (j == k) v[i][j][k] -= map[j][i - j + 1];
			}
	if (xk <= xs && yk <= ys) {
		if (xk == xs && yk == ys) ans = u[xk + yk - 1][xk][xk];
		else ans = v[xk + yk - 1][xk][xk];
	} else {
		if (xk > xs) {
			for (int i = 1; i < min(ys, xs + 1); i ++)
				ans = max(ans, v[xs + i - 1][xs][xs] + g[xs + 1][i]);
			if (xs >= ys) ans = max(ans, u[xs + ys - 1][xs][xs] + g[xs + 1][ys]);
		}
		if (yk > ys) {
			for (int i = 1; i < min(xs, ys + 1); i ++)
				ans = max(ans, v[ys + i - 1][i][i] + g[i][ys + 1]);
			if (ys >= xs) ans = max(ans, u[xs + ys - 1][xs][xs] + g[xs][ys + 1]);
		}
	}
	printf("%lld", ans);
	return 0;
}

过了大样例也还是只有30分怎么办啊啊q

2021/9/20 13:37
加载中...