Problem

给你一个2*n的矩阵，要求你用补充叠的矩阵去框，要求每个矩阵框中的数之和为0，问最多可以用几个矩阵。

Solution

首先预处理出一个点到离它最近的一段和为0的区间的左端点

然后到这往前用记忆化搜索的方式DP就可以了

Notice

注意要记忆化

Code

#include<map>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define sqz main

#define ll long long

#define reg register int

#define rep(i, a, b) for (reg i = a; i <= b; i++)

#define per(i, a, b) for (reg i = a; i >= b; i--)

#define travel(i, u) for (reg i = head[u]; i; i = edge[i].next)

const int INF = 1e9, N = 300000;

const double eps = 1e-6, phi = acos(-1);

ll mod(ll a, ll b) {if (a >= b || a < 0) a %= b; if (a < 0) a += b; return a;}

ll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();

if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}

void write(ll y) { if (y < 0) putchar('-'), y = -y; if (y > 9) write(y / 10); putchar(y % 10 + '0');}

map<ll, int> Derec;

map<pair<int, int>, int> F;

int Pre[3][N + 5];

ll T[3][N + 5];

int Solve(int n, int m)

{

	if (!~Pre[1][n] && !~Pre[2][m] && !~Pre[0][min(n, m)]) return 0;

	pair<int, int> P(n, m);

	if (F.count(P)) return F[P];

	int ans = 0;

	if (Pre[1][n] > Pre[2][m]) ans = max(ans, Solve(Pre[1][n], m) + 1);

	else if (~Pre[2][m])ans = max(ans, Solve(n, Pre[2][m]) + 1);

	if (~Pre[0][min(n, m)]) ans = max(ans, Solve(Pre[0][min(n, m)], Pre[0][min(n, m)]) + 1);

	return F[P] = ans;

}

int sqz()

{

	int n = read();

	rep(i, 1, n) T[0][i] += (T[1][i] = read());

	rep(i, 1, n) T[0][i] += (T[2][i] = read());

	rep(i, 0, 2)

		rep(j, 1, n) T[i][j] = T[i][j - 1] + T[i][j];

	rep(i, 0, 2)

	{

		Derec.clear(); Derec[0] = 0;

		Pre[i][0] = -1;

		rep(j, 1, n)

		{

			Pre[i][j] = max(Pre[i][j - 1], Derec.count(T[i][j]) ? Derec[T[i][j]] : -1);

			Derec[T[i][j]] = j;

		}

	}

	printf("%d\n", Solve(n, n));

}

巴特西

[Codeforces771E]Bear and Rectangle Strips

Problem

Solution

Notice

Code

最新文章

热门文章