「校内训练2019-09-08」序列

Description

给你$n$个序列,序列不等长,每个序列可以把第一个放到最后。
现在你不能改变两个序列的顺序,每两个序列收尾相接的贡献为,$i$序列的结尾和$i+1$序列的开头的差值。
请你最大化贡献。

Data Range

tot表示序列的总长度。
$1\leq tot \leq 10^6,$

Solution

每次肯定是相邻的两个数作为首和尾,$(a[i+1],a[i])$作为一个二元组。
$DP$方程:$f[i]=max(f[j]+|a[i].first-a[j].second|)$
然后我们把$abs$由大小分开讨论。
会得到两个式子
然后再序列内将所有的二元组按照$second$排序,然后做序列内前缀最大和后缀最大,二分找到前一个最大值。
时间复杂度为$nlogn$。

Code

#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

template <typename T> void read(T& x) {
    x = 0; char ch = 0; bool flg = 0; 
    for (; !isdigit(ch); ch = getchar())
        flg |= ch == '-';
    for (; isdigit(ch); ch = getchar())
        x = x * 10 + (ch ^ 48);
    flg ? x *= -1 : 233;
}

const int N = 1e6 + 5;

int n, m; 
pair<int, int> a[N], tmp[N];
int lb[N], rb[N], bel[N], b[N], f[N], sq[N];
int prefix[N], suffix[N];

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

void solve() {
    memset(suffix, 0, sizeof suffix);
    memset(prefix, 0, sizeof prefix);
    read(n); 
    m = 0; 
    for (int i = 1, len; i <= n; i++) {
        read(len); 
        lb[i] = m + 1; 
        rb[i] = m + len; 
        for (int j = 1; j <= len; j++) {
            read(b[j]); 
            bel[j + m] = i; 
        }
        for (int j = 1; j < len; j++) 
            tmp[j] = {b[j + 1], b[j]};
        tmp[len] = {b[1], b[len]};
        sort(tmp + 1, tmp + 1 + len, cmp); 
        for (int j = 1; j <= len; j++) {
            a[++m] = tmp[j];
        }
    }
    int ans = 0;
    for (int i = 1; i <= m; i++) {
        int l = lb[bel[i] - 1], r = rb[bel[i] - 1];  
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (a[mid].second >= a[i].first) 
                r = mid - 1; 
            else 
                l = mid + 1; 
        }
        int res = l; 
        f[i] = max(suffix[res] - a[i].first * (bel[i] - 1), prefix[res - 1] + a[i].first * (bel[i] - 1)); 
        if (i == rb[bel[i]]) {
            int l = lb[bel[i]], r = rb[bel[i]];
            prefix[l] = f[l] - a[l].second * bel[l];
            suffix[r] = f[r] + a[r].second * bel[r];
            for (int j = l + 1; j <= r; j++) 
                prefix[j] = max(prefix[j - 1], f[j] - a[j].second * bel[j]);
            for (int j = r - 1; j >= l; j--) 
                suffix[j] = max(suffix[j + 1], f[j] + a[j].second * bel[j]); 
        }
        ans = max(ans, f[i]);
    }
    printf("%lld\n", ans); 
}

signed main() {
    int T; 
    read(T); 
    while (T--) {
        solve(); 
    }
    return 0; 
}
最后修改:2019 年 09 月 10 日 08 : 41 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论