题解：P13789 「CZOI-R6」游戏

题目大意

有

q

局游戏，每局游戏会给一个坐标

(x_i,y_i)

，然后每个

n \times m

矩阵中的点

(a,b)

，都会有一个得分

u_i + k_1 \cdot \lvert x_i - a \rvert + k_2 \cdot \lvert y_i - b\rvert

，对于每个点，求其在这

q

局游戏中得分的最大值。

分析

考虑对于每个点算答案，把左上、左下、右上、右下四个方向分开算得分，然后取

\max

，这样就把绝对值拆掉了，讨论正负号即可。

以左下为例，得分就是：

u_i - k_1 \cdot x_i - k_2 \cdot y_i + k_1 \cdot a + k_2 \cdot b

枚举

(a,b)

，右边两项就是固定的了，只需要对每局游戏的求左边三项和再取

\max

。

这就转化成了一个二位偏序问题：查找左下角的

(x,y)

的贡献的最大值。

这里我当时没多想，直接按

x

从小到大枚举，再用两个树状数组查前后缀最大值，其实直接预处理前后缀最大值就行了。

时间复杂度

O(n^2)

，我用的树状数组还得多个 log。

code

CPP

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

ll read()
{
    ll ret = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) f = (ch == '-' ? -f : f), ch = getchar();
    while (isdigit(ch)) ret = ret * 10 + ch - '0', ch = getchar();
    return ret * f;
}

int n ,m ,t;
ll k1 ,k2;
const int N = 3e3 + 10 ,M = 1e6 + 10;
const ll inf = 1e18;
struct node{
	ll x ,y ,u;
} q[M];
ll f[N][N];

//树状数组 
ll c1[N] ,c2[N];
#define lowbit(x) x & -x
void add1(ll *c ,int x ,ll k) { while (x < N) c[x] = max(c[x] ,k) ,x += lowbit(x); }
void add2(ll *c ,int x ,ll k) { while (x) c[x] = max(c[x] ,k) ,x -= lowbit(x); }
ll qry1(ll *c ,int x)
{
	ll ret = -inf;
	while (x) ret = max(ret ,c[x]) ,x -= lowbit(x);
	return ret;
}
ll qry2(ll *c ,int x)
{
	ll ret = -inf;
	while (x < N) ret = max(ret ,c[x]) ,x += lowbit(x);
	return ret;
}

ull qpow(ull a ,ull b)
{
	ull ret = 1;
	while (b)
	{
		if (b & 1) ret *= a;
		a *= a;
		b >>= 1;
	}
	return ret;
}

int main()
{
	n = read() ,m = read() ,t = read() ,k1 = read() ,k2 = read();
	for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) f[i][j] = -inf;
	
	for (int i = 1;i <= t;i++) q[i] = {read() ,read() ,read()};
	
	//按 x 坐标排序 
	sort(q + 1 ,q + 1 + t ,[](node a ,node b){ return a.x == b.x ? a.y < b.y : a.x < b.x; });
	
	for (int i = 0;i < N;i++) c1[i] = c2[i] = -inf;
	int now = 1;
	for (int i = 1;i <= n;i++) //x从小到大，计算左下、左上 
	{
		while (now <= t && q[now].x == i)
		{
			add1(c1 ,q[now].y ,q[now].u - q[now].x * k1 - q[now].y * k2);
			add2(c2 ,q[now].y ,q[now].u - q[now].x * k1 + q[now].y * k2);
			now++;
		}
		for (int j = 1;j <= m;j++)
			f[i][j] = max(f[i][j] ,i * k1 + j * k2 + qry1(c1 ,j)) ,
			f[i][j] = max(f[i][j] ,i * k1 - j * k2 + qry2(c2 ,j));
	}
	
	for (int i = 0;i < N;i++) c1[i] = c2[i] = -inf;
	now = t;
	for (int i = n;i >= 1;i--) //x从大到小，计算右下、右上 
	{
		while (now >= 1 && q[now].x == i)
		{
			add1(c1 ,q[now].y ,q[now].u + q[now].x * k1 - q[now].y * k2);
			add2(c2 ,q[now].y ,q[now].u + q[now].x * k1 + q[now].y * k2);
			now--;
		}
		for (int j = 1;j <= m;j++)
			f[i][j] = max(f[i][j] ,-i * k1 + j * k2 + qry1(c1 ,j)) ,
			f[i][j] = max(f[i][j] ,-i * k1 - j * k2 + qry2(c2 ,j));
	}
	
	ull ans = 0; //用自然溢出算答案 
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= m;j++)
			ans += f[i][j] * qpow(131 ,1LL * (i - 1) * m + j);
	
	printf("%llu\n",ans);
	
    return 0;
}

题解：P13789 「CZOI-R6」游戏

文章操作

题目大意

分析

code

相关推荐

评论

题解：P13789 「CZOI-R6」游戏