题解：CF2159D2 Inverse Minimum Partition (Hard Version)

~~我是小菜鸡 Div.2 rk60+~~

通过模拟我们可以发现一下几个性质。

我们设

a

的值域为

V

。

$f[l, r]$ 不大于 $f[l - x, r] , x > 0$ 。
任意 $f[l, r]$ 不大于 $2\log(V)≤128$ 。
总有一个最优解，只使用成本最多为 $3$ 的子数组。

定义

g_{i, r}

表示，以

r

为右端点，使用

1

次成本为

i

的子数组能到达的最左边的位置，由于性质3，

1≤i≤3

，可以使用线段树或者 $RMQ$ + 二分求出

g

数组。

设

dp_{i, r}

表示右端点为

r

的时候，代价

f[l,r] ≤ i

的最小

l

，由于性质

2

，

i ≤ 128

，我们有转移。

$dp_{𝑐,𝑟}=𝑟+1$ （当 $𝑐≤0$ 时）。
$dp_{𝑐,𝑟}=\min_{1≤𝑘≤3}(min_{max((dp_{𝑐−𝑘,𝑟})−1,1)≤𝑖≤𝑟}g_{i,k})$ （当 $𝑐>0$ 时）。

根据性质

1

的单调性我们可以知道，最终答案

ans = \sum_{r=1}^{n}\sum_{j=1}^{128} (dp_{j-1,r} - dp_{j,r}) \times j

。

code

CPP

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

#define ll long long

const int N = 400005;
const int mod = 1000000007;
const int INF = 0x3f3f3f3f;

int T, n;
ll a[N], mn[N][20];
int lg[N], st[4][N][20], f[130];

int st_query(int k, int l, int r) {
   int len = lg[r - l + 1];
   return min(st[k][l][len], st[k][r - (1 << len) + 1][len]);
}

ll get(int l, int r) {
   int len = lg[r - l + 1];
   return min(mn[l][len], mn[r - (1 << len) + 1][len]);
}

int binary(int R, ll x) { // 1 ~ r 范围内使得 min[i ~ r] >= x 大最小的i  
   int l = 1, r = R;
   while (l <= r) {
       int mid = (l + r) >> 1;
       if (get(mid, R) < x) l = mid + 1;
       else r = mid - 1;
   }
   return l;
}

int main() {
   
   for (int i = 2; i < N; i++) lg[i] = lg[i >> 1] + 1;

   int T;
   scanf("%d", &T);
   while (T--) {
       scanf("%d", &n);
       int t = 0;
       for (int i = 1; i <= n; i++) {
           scanf("%lld", &a[i]);
       }
       
       for (int i = 1; i <= n; i++) mn[i][0] = a[i];
       for (int i = 1; (1 << i) <= n; i++) {
           for (int j = 1; j + (1 << i) - 1 <= n; j++) {
               mn[j][i] = min(mn[j][i - 1], mn[j + (1 << (i - 1))][i - 1]);
           }
       }

       // get the array of L 
       for (int r = 1; r <= n; r++) {
           for (int i = 1; i <= 3; i++) {
               st[i][r][0] = binary(r, (a[r] + i - 1) / i);
           }
       }

       for (int k = 1; k <= 3; k++) {
           for (int i = 1; (1 << i) <= n; i++) {
               for (int j = 1; j + (1 << i) - 1 <= n; j++) {
                   st[k][j][i] = min(st[k][j][i - 1], st[k][j + (1 << (i - 1))][i - 1]);
               }
           }
       }

       ll ans = 0;
       for (int r = 1; r <= n; r++) {
           f[0] = r + 1;
           for (int i = 1; i <= 128; i++) {
               f[i] = INF;
               for (int k = 1; k <= min(i, 3); k++) {
                   f[i] = min(st_query(k, max(f[i - k] - 1, 1), r), f[i]);
               }
           }
           for (int i = 1; i <= 128; i++) {
               ans += (f[i - 1] - f[i]) * i;
           }
       }
       printf("%lld\n", ans);
   }
   return 0;
}

题解：CF2159D2 Inverse Minimum Partition (Hard Version)

文章操作

code

相关推荐

评论

题解：CF2159D2 Inverse Minimum Partition (Hard Version)