社区讨论

memset的小问题

NNeovim
P5752 [NOI1999] 棋盘分割参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo7kk1yb
此快照首次捕获于
2023/10/27 03:20
2 年前
此快照最后确认于
2023/10/27 03:20
2 年前
查看原帖
记搜初始化的时候（double 数组）
memset(f, 127, sizeof f) 会 TLE on #5.
memset(f, -1, sizeof f) Accepted.
有没有大佬解释一下为啥
memset 成 -1 为啥会快很多？
TLE
CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 15, M = 9;
int n, m = 8;
int s[M][M];
double f[M][M][M][M][N];
double xbar;

double get(int x1, int y1, int x2, int y2)
{
	double sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] - xbar;
	return sum * sum / n;
}

double dp(int x1, int y1, int x2, int y2, int k)
{
	double &v = f[x1][y1][x2][y2][k];
	if (v != f[0][0][0][0][0]) return v;
	if (k == 1) return v = get(x1, y1, x2, y2);
	for (int i = x1; i < x2; i ++ )
	{
		v = min(v, dp(x1, y1, i, y2, k - 1) + get(i + 1, y1, x2, y2));
		v = min(v, dp(i + 1, y1, x2, y2, k - 1) + get(x1, y1, i, y2));
	}
	for (int i = y1; i < y2; i ++ )
	{
		v = min(v, dp(x1, y1, x2, i, k - 1) + get(x1, i + 1, x2, y2));
		v = min(v, dp(x1, i + 1, x2, y2, k - 1) + get(x1, y1, x2, i));
	}
	return v;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= m; i ++ )
		for (int j = 1; j <= m; j ++ )
		{
			cin >> s[i][j];
			s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
		}
	memset(f, 127, sizeof f);
	xbar = (double)s[m][m] / n;
	printf("%.3lf\n", sqrt(dp(1, 1, m, m, n)));
	return 0;
}
AC
CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 15, M = 9;
int n, m = 8;
int s[M][M];
double f[M][M][M][M][N];
double xbar;

double get(int x1, int y1, int x2, int y2)
{
	double sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] - xbar;
	return sum * sum / n;
}

double dp(int x1, int y1, int x2, int y2, int k)
{
	double &v = f[x1][y1][x2][y2][k];
	if (v >= 0) return v;
	if (k == 1) return v = get(x1, y1, x2, y2);
	v = 2e9;
	for (int i = x1; i < x2; i ++ )
	{
		v = min(v, dp(x1, y1, i, y2, k - 1) + get(i + 1, y1, x2, y2));
		v = min(v, dp(i + 1, y1, x2, y2, k - 1) + get(x1, y1, i, y2));
	}
	for (int i = y1; i < y2; i ++ )
	{
		v = min(v, dp(x1, y1, x2, i, k - 1) + get(x1, i + 1, x2, y2));
		v = min(v, dp(x1, i + 1, x2, y2, k - 1) + get(x1, y1, x2, i));
	}
	return v;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= m; i ++ )
		for (int j = 1; j <= m; j ++ )
		{
			cin >> s[i][j];
			s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
		}
	memset(f, -1, sizeof f);
	xbar = (double)s[m][m] / n;
	printf("%.3lf\n", sqrt(dp(1, 1, m, m, n)));
	return 0;
}

回复

共 2 条回复，欢迎继续交流。

正在加载回复...