【JOISC 2020 Day3】Constellation 3
程序员文章站
2024-03-19 08:24:34
...
题目
题目描述
题目译自 JOISC 2020 Day3 T1「星座 3 / Constellation 3」,感谢 @Chanis 提供翻译。
JOI 君拍了一张 的星空图,将左起第 列,下起第 行的像素点称为像素 。
画面里有白色的大楼,黄色的星星,黑色的空格。第 列从最下方到自下数起第 行都是白色的大楼。有 个星星,第 个星星位于像素点 。此外,所有的像素点都是黑色。
若一个长方形区域可以称作星座,则满足以下条件:
不含白色像素点。
至少存在两个星星。
看厌了星座的 JOI 君要把一些黄色的星星涂成黑色,使得没有星座存在。将第 个星星涂成黑色会使照片的不自然度增加 ,最初不自然度为 。求不自然度的最小值。
输入格式
输入第一行为一个整数 ,表示地图的边长大小。
第二行为 个整数 ,描述如题目。
第三行为一个整数 ,表示星星的个数。
接下来的 行,每行三个整数 ,即对第 个星星的描述。
输出格式
输出不自然度的最小值。
样例
样例输入 1
5
1 3 4 2 3
3
1 5 3
4 3 2
2 4 2
样例输出 1
2
样例解释 1
QQ图片20200322145805.png
可以发现把第三个星删了之后它就和一号构不成星座,且比删去一号花费少。
样例输入 2
7
5 6 2 3 6 7 6
5
7 7 5
3 3 7
3 7 10
1 7 6
4 7 8
样例输出 2
16
样例解释 2
删去三号和四号。
数据范围与提示
对于 的数据,,保证:
;
;
;
;
。
详细子任务及附加限制如下表:
子任务编号 附加限制 分值
无附加限制
思路
用分治建树,然后在树上跑一个DP
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define int long long
using namespace std;
struct node {
int t,x;
bool operator<(const node &a) const { return t > a.t; }
};
node point[400001];
int fa[400001][31],sum,l[400001],r[400001],d[400001],k[400001],u[400001],deque[400001],f,top,n,m,
a[400001];
int rt,res,dp[400001],c[400001],dfn[400001],ed[400001],length,maxn;
vector<int> P[400001];
int lowbit(int x) { return x & (-x); }
void add(int x,int y) {
for (; x <= n; x += lowbit(x)) c[x] += y;
return;
}
int Sum(int x) {
res = 0;
for (; x >= 1; x -= lowbit(x)) res += c[x];
return res;
}
void DFS(int x) {
dfn[x] = ++length;
if (l[x])
DFS(l[x]);
if (r[x])
DFS(r[x]);
ed[x] = length;
dp[x] = dp[l[x]] + dp[r[x]];
add(dfn[x],dp[x]);
add(ed[x] + 1,-dp[x]);
for (int i = 0; i < P[x].size(); ++i) dp[x] = max(dp[x],Sum(dfn[k[P[x][i]]]) + u[P[x][i]]);
maxn = max(maxn,dp[x]);
add(dfn[x],-dp[x]);
add(ed[x] + 1,dp[x]);
return;
}
signed main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
a[n + 1] = n + 1;
rt = n + 1;
n++;
for (int i = 1; i <= n; ++i) {
f = 0;
while (top > 0 && a[deque[top]] <= a[i]) {
f = deque[top];
top--;
}
l[i] = f;
if (f != 0)
fa[f][0] = i;
if (top > 0) {
r[deque[top]] = i;
fa[i][0] = deque[top];
}
deque[++top] = i;
}
for (int j = 1; j <= 30; ++j)
for (int i = 1; i <= n; ++i) fa[i][j] = fa[fa[i][j - 1]][j - 1];
cin >> m;
int x,y,z;
for (int i = 1; i <= m; ++i) {
cin >> k[i] >> y >> u[i];
sum += u[i];
d[i] = k[i];
for (int j = 30; j >= 0; --j)
if (fa[d[i]][j] != 0 && a[fa[d[i]][j]] < y)
d[i] = fa[d[i]][j];
P[d[i]].push_back(i);
}
DFS(rt);
cout << sum - maxn << endl;
return 0;
}