CF1208E Let Them Slide

发表于 | 阅读数

有$n$个数组和一个长为$w$宽为$n$的矩阵。给出这$n$个数组，现在将这个$n$个数组放在矩阵上，每个数组占用一行，并且每一个数组中的每一个位置都在矩阵范围内。对于第ii列，我们可以通过合理安排使得这一列中所有元素之和尽可能大，记这个最大值为$s_i$,求出所有$s$的值。

每行判断最左边靠到哪里，最后靠到哪里。

  • $\max{(RMQ[j-(n-len),j])}或者\max{(RMQ[1,j],0)}$（一个可以取到$0$,一个取不到。)
  • 然后倒过来再搞一遍。是对称的。
  • $n>2len$，显然$[len+1,n-len]$都可以随意取。
    代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75



#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
                                                            using namespace std;
typedef long long ll;
const int N = 2e6 + 100;
const int mod = 1e9 + 7;
int n, st[N][30];
int a[N];
void init()
{
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= 20; j++)
            st[i][j] = 0;
    for (int i = 1; i <= n; i++)
        st[i][0] = a[i];
    for (int j = 1; j <= 20; j++)
        for (int i = 1; i <= n; i++)
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int rmq(int l, int r)
{
    int p = int(log(r - l + 1) / log(2.0));
    return max(st[l][p], st[r - (1 << p) + 1][p]);
}
int h, w;
ll ans[N];
int main()
{
    scanf("%d%d", &h, &w);
    while (h--)
    {
        scanf("%d", &n);
        for (int j = 1; j <= n; j++)
            scanf("%d", &a[j]);
        init();
        int ko = w - n;
        int mx;
        for (int j = 1; j <= n; j++)
        {
            if (j - ko < 1)
                mx = max(0, rmq(1, j));
            else
                mx = rmq(j - ko, j);
            ans[j] += mx;
            ans[j + 1] -= mx;
        }
        for (int j = max(w - n + 1, n + 1); j <= w; j++)
        {
            int s = w - j + 1;
            mx = max(0, rmq(n - s + 1, n));
            ans[j] += mx;
            ans[j + 1] -= mx;
        }
        if (w > 2 * n)
        {
            ans[n + 1] += max(0, rmq(1, n));
            ans[w - n + 1] -= max(0, rmq(1, n));
        }
    }
    ll p = 0;
    for (int i = 1; i <= w; i++)
    {
        p += ans[i];
        printf("%lld ", p);
    }
}

</details>