题解 P2545 【[AHOI2004]实验基地】

aha浮云 · 2018-11-06 14:03:09 · 题解

话说这个题直接暴力啊，，

就是在一个矩形里挖一块小矩形

那么先对两行求个前缀和

问题就转换为求上面那个数列的最小子段和

那么很显然了

暴力嘛， 直接上线段树

然后复杂度就从n^2 变成了n^2 * log2n 勉强卡过（全场最慢什么鬼qwq） 下面是代码

#include<bits/stdc++.h>
using namespace std;
const int max_n = 2010;
int a[max_n], b[max_n], sum[max_n];
int n, cnt, tot;
struct Node
{
    int l, r, front, behind, val, sum;
    Node *lc, *rc;
}node1[max_n * 4], node2[max_n * 4], A[max_n];
void Push_Up1(Node *root)
{
    root->val = min(root->lc->val, root->rc->val);
    root->val = min(root->val, root->lc->behind + root->rc->front);
    root->sum = root->lc->sum + root->rc->sum;
    root->front = min(root->lc->front, root->lc->sum + root->rc->front);
    root->behind = min(root->rc->behind, root->lc->behind + root->rc->sum);
}
void buildtree1(Node *root, int L, int R)
{
    root->l = L, root->r = R;
    int mid = (L + R) >> 1;
    if(L == R) 
    {
        root->sum = a[L];
        root->front = root->behind = a[L];
        root->val = a[L];
        return;
    }
    root->lc = &node1[++ cnt];
    root->rc = &node1[++ cnt];
    buildtree1(root->lc, L, mid);
    buildtree1(root->rc, mid + 1, R);
    Push_Up1(root);
}
Node Query1(Node *root, int L, int R)
{
    if(root->l == L && root->r == R)
    return *root;
    int mid = (root->l + root->r) >> 1;
    if(R <= mid) return Query1(root->lc, L, R);
    else if(L > mid) return Query1(root->rc, L, R); 
    else 
    {
        Node t, t1, t2;
        t1 = Query1(root->lc, L, mid);
        t2 = Query1(root->rc, mid + 1, R);
        t.lc = &t1, t.rc = &t2;
        Push_Up1(&t);
        return t;
    } 
}
int main()
{
    cin >> n;
    for(int i = 1;i <= n; i++)
    scanf("%d", &a[i]);
    for(int i = 1;i <= n; i++)
    scanf("%d", &b[i]);
    for(int i = 1;i <= n; i++)
    sum[i] = sum[i - 1] + a[i] + b[i];
    buildtree1(node1, 1, n);
//  for(int i = 1;i <= cnt; i++)
//  printf("%d %d %d %d %d %d\n", node1[i].l, node1[i].r, node1[i].sum, node1[i].val, node1[i].front, node1[i].behind);
    int Ans = -0x7f7f7f7f;
    for(int i = 1;i <= n; i++)
        for(int j = i + 2;j <= n; j++)
            Ans = max(Ans, sum[j] - sum[i - 1] - Query1(node1, i + 1, j - 1).val);
    cout << Ans << endl;
    return 0;
}

是不是很暴力啊