比赛 CSP2023-J模拟赛 评测结果 AAATTTTTTT
题目名称 复制题目 最终得分 30
用户昵称 usr10086 运行时间 7.438 s
代码语言 C++ 内存使用 119.84 MiB
提交时间 2023-10-18 20:04:33
显示代码纯文本
#include <bits/stdc++.h>

using namespace std;

const int N = 310;

ifstream fin("copy.in");
ofstream fout("copy.out");
#define cin fin
#define cout fout

int n, m, dp[N][N][N], mk[N][N];
char mp[N][N];

void chmin(int& a, int b)
{
	if (b < a) a = b;
}

int solve(int x1, int y1)
{
	if (mp[x1][y1] == ')') return 0;

	dp[x1][y1][1] = 1;
	for (int i = x1; i <= n; i++)
	for (int j = y1; j <= m; j++)
		for (int k = 0; k <= i+j-x1-y1+1; k++)
		{
			if (mp[i+1][j] == ')' && k>0) chmin(dp[i+1][j][k-1], dp[i][j][k]);
			else if (mp[i+1][j] == '(') chmin(dp[i+1][j][k+1], dp[i][j][k]+(i-x1+j-y1+2));
			if (mp[i][j+1] == ')' && k>0) chmin(dp[i][j+1][k-1], dp[i][j][k]);
			else if (mp[i][j+1] == '(') chmin(dp[i][j+1][k+1], dp[i][j][k]+(i-x1+j-y1+2));
		}
	int ans = 0;
	for (int i = x1; i <= n; i++)
		for (int j = y1; j <= m; j++)
			if (dp[i][j][0] != 0x3f3f3f3f) ans = max(ans, (i-x1+j-y1+1)*(i-x1+j-y1+2)/2 - 2*dp[i][j][0]), mk[i][j] = true;
	for (int i = x1; i <= n; i++)
		for (int j = y1; j <= m; j++)
			for (int k = 0; k <= i+j-x1-y1+1; k++)
				dp[i][j][k] = 0x3f3f3f3f;
//	printf("solve(%lld, %lld) = %lld\n", x1, y1, ans);
	return ans;
}

signed main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> mp[i]+1;
	memset(dp, 0x3f, sizeof dp);
	int ans = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (!mk[i][j]) ans = max(ans, solve(i, j));
	cout << ans;
}