AcWing 5295. 三元组
原题链接
中等
作者:
kanm7
,
2023-11-18 20:37:22
,
所有人可见
,
阅读 153
可以将题目中的sum(l,r)转化一下,变成sum(l,r) = s(l,r) - a[r],s用于前缀和,a表示单点,然后就可以化简了。同时,由于题目下标从0开始,而我们要从1开始,所以1<=x<=y<=z<=n+1。 之后,我们将原式转化一下。首先我们定义,d[x] = s[x] + s[x - 1] - a[x],等号右式可以先化简一下,很好得出。然后我们最终将原式转化成为求d[x] - d[y] + d[z]的最小值,由于n只有5000,所以我们可以固定x,z,然后O(1)求出y,那怎么求y呢?可以利用rmq,快速处理。所以我们球的就是最小的d[y]。
#include <bits/stdc++.h>
#define LL long long
#define int LL
#define INF 0x3f3f3f3f
#define PII pair<int,int>
#define pcc pair<char,char>
#define x first
#define y second
#define inf 1e18
#define kanm7 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 5010, P = 13;
int f[N][P], id[N][P];
int H[N];
int s[N], d[N], a[N];
int n;
void st() {
int cnt = 0;
for(int i = 1; i <= n + 1; i *= 2)
{
H[i] = cnt ++;
}
for(int i = 1; i <= n + 1; i ++)
{
if(!H[i]) H[i] = H[i - 1];
}
for(int j = 0; j < P; j ++) {
for(int i = 1; i + (1 << j) - 1 <= n + 1; i ++) {
if(!j) {
f[i][j] = d[i];
id[i][j] = i;
} else {
// f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
if(f[i][j - 1] < f[i + (1 << (j - 1))][j - 1]) {
f[i][j] = f[i][j - 1];
id[i][j] = id[i][j - 1];
} else {
f[i][j] = f[i + (1 << (j - 1))][j - 1];
id[i][j] = id[i + (1 << (j - 1))][j - 1];
}
}
}
}
}
void solve() {
cin >> n;
// cout << n << endl;
for(int i = 1; i <= n; i ++) {
cin >> s[i];
a[i] = s[i];
}
for(int i = 1; i <= n + 1; i ++) {
s[i] += s[i - 1];
}
a[n + 1] = 0;
for(int i = 1; i <= n + 1; i ++) {
d[i] = s[i] + s[i - 1] - a[i];
}
st();
int all = s[n + 1];
int ma = -inf;
vector<int> ans;
for(int x = 1; x <= n + 1; x ++) {
for(int z = x; z <= n + 1; z ++) {
int sum = d[x] + d[z];
int k = H[z - x + 1];
int y;
if(f[x][k] < f[z - (1 << k) + 1][k]) {
sum -= f[x][k];
y = id[x][k];
} else {
sum -= f[z - (1 << k) + 1][k];
y = id[z - (1 << k) + 1][k];
}
sum -= all;
// cout << sum << ' ' << x << ' ' << y << ' ' << z << endl;
if(sum > ma) {
ma = sum;
ans.clear();
ans.push_back(x - 1);
ans.push_back(y - 1);
ans.push_back(z - 1);
// for(auto it : ans) {
// cout << it << ' ' ;
// }
// cout << endl;
}
}
}
// cout << ma << endl;
// cout << d[1] - a[1] - (d[1] - a[1]) + d[2] - a[2] - all<< endl;
cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << endl;
}
signed main() {
kanm7;
int T = 1;
// cin >> T;
while(T --) {
solve();
}
return 0;
}
转化成d[x] - d[y] + d[z],可以枚举中间点y,然后往左边找x,往右边找z。写法更简单。哎,还是太笨了。