Codeforces Round #842 (Div. 2)

Author：我不会玩锐雯
发布时间：February 16, 2023
725views
No comments
10195字数
Categories： ACM技能点

情况比赛链接：https://codeforces.com/contest/1768

A. Greatest Convex

题意：给定一个整数$k$，查找小于$k$的最大整数$x$，要求$x!+(x-1)!$是$k$的倍数。

解法： $(k-1)!+(k-2)! = (k-1) \times (k-2)!+(k-2)! = k \times (k-2)!$，答案始终为$k-1$。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
int n;
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        printf("%d\n", n - 1);
    }
    return 0;
}

B. Quick Sort

题意：给定一个长度为$n$的全排列，每次操作选择$k$个元素，删除它们后按递增顺序添加到排列的末尾。求出按升序对排列进行排序所需的最少操作数。

解法：假设有$x$个元素不参与任何操作，那么在最终数组中这$x$个元素将按原来的顺序排在数组的开头。最终数组按升序排列，则这$x$个元素在原数组中是形如$[1,2,3...]$的子序列。为了使操作次数最少，则$x$最大。换而言之在原数组中找出形如$[1,2,3...]$的最长子序列，然后从小到大依次删除不在子序列中的元素，最少的操作次数为$\lceil\frac{n - x}{k}\rceil=\lfloor \frac{n - x + k - 1}{k} \rfloor$。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
int n, k;
int a[MAXN];
void solve() {
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);

    int cnt = 0;//子序列长度
    for(int i = 0; i < n; i++) {
        if(a[i] == cnt + 1) cnt++;
    }

    int ans = (n - cnt + k - 1) / k;
    printf("%d\n", ans);
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

C. Elemental Decompress

题意：给定一个包含$n$个整数的数组$a$。需要求出两个全排列$p$和$q$满足$\max(p_i,q_i)=a_i$。

解法：一种方式是将$a$中的元素选择性的放入到$p$中或$q$中。从小到大遍历$a$中的元素，如果$a[i]$在$p$中没有被使用且$q$中有小于等于$a[i]$的元素没有被使用，则将$a[i]$放置到$p$中并且$q$选择最小的可以使用的元素。放置在$q$中的情况和$p$一样，如果$p$和$q$均无法放置则无解。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
int n;
struct node {
    int id;
    int x;
} a[MAXN];
bool f1[MAXN], f2[MAXN];
int ans1[MAXN], ans2[MAXN];
bool cmp(node a, node b) {
    return a.x < b.x;
}
bool cal() {
    int id1 = 1, id2 = 1;
    for(int i = 0; i <= n; i++) f1[i] = f2[i] = false;

    for(int i = 0; i < n; i++) {
        int target = a[i].x;
        if(!f1[target]) {//尝试放入p中
            while(id2 <= target && f2[id2]) {
                id2++;
            }
            if(id2 <= target) {
                ans1[a[i].id] = target;
                ans2[a[i].id] = id2;
                f1[target] = true;
                f2[id2] = true;
                continue;
            }
        }

        if(!f2[target]) {//尝试放入q中
            while(id1 <= target && f1[id1]) {
                id1++;
            }
            if(id1 <= target) {
                ans1[a[i].id] = id1;
                ans2[a[i].id] = target;
                f1[id1] = true;
                f2[target] = true;
                continue;
            }
        }

        return false;
    }
    return true;
}
void solve() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        a[i].id = i;
        scanf("%d", &a[i].x);
    }
    sort(a, a + n, cmp);

    if(cal()) {
        puts("YES");
        for(int i = 0; i < n; i++) printf("%d ", ans1[i]);
        putchar(10);
        for(int i = 0; i < n; i++) printf("%d ", ans2[i]);
        putchar(10);
        return;
    }
    puts("NO");
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

D. Lucky Permutation

题意：给定一个全排列，每次操作交换任意两个元素，问最少交换多少次使得排列逆序数恰好为1。

解法：从有向图的角度来看整个排列，对每个元素建立有向边$i \rightarrow a_i$，整个图由$k$个有向环构成。可以先使整个排列交换成升序，然后交换任意两个相邻的元素来使得排列逆序数恰好为1，这样的方式需要的操作次数为$n-k+1$。但如果一个有向环中存在相邻的两个元素，可以使得这两个相邻元素始终在同一个有向环中，那么最终得到的排列逆序数恰好为1，所需要的操作次数为$n-k-1$。换而言之，如果所有的有向环中都没有两个相邻的元素，那么将整个排列升序然后交换任意两个相邻的元素，否则保留任意一个有向环中两个相邻的元素使其形成逆序对。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
int n;
int a[MAXN];
int f[MAXN];
void dfs(int i, int root) {
    do {
        f[i] = root;
        i = a[i];
    } while(i != root);
}
void solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        f[i] = i;
    }

    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        if(f[i] == i) {//首次遍历环
            cnt++;
            dfs(i, i);
        }
    }

    for(int i = 1; i < n; i++) {
        if(f[i] == f[i + 1]) {//环中存在相邻的元素
            printf("%d\n", n - cnt - 1);
            return;
        }
    }

    printf("%d\n", n - cnt + 1); //环中没有相邻的元素
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

E. Partial Sorting

题意：考虑长度为 $3n$ 的排列 $p$。每次可以进行以下操作之一：按递增顺序对前 $2n$ 个元素进行排序；按递增顺序对最后 $2n$ 个元素进行排序。定义 $f(p)$ 为使排列 $p$ 以递增顺序排序所需操作的最小次数。求所有排列的 $f(p)$ 之和。

解法：注意到对于任意排列最多执行3次操作，可以把排列按操作次数的不同分别计数，然后分别计算对答案的贡献即可。

$f(p) = 0$，有且只有一个排列不需要操作，个数为$1$。
$f(p) \leq 1$，当前$n$个数已经升序或者后$n$个数已经升序时需要的操作次数不超过1，个数为$2 \times (2n!) - (n!)$。
$f(p) \leq 2$，当前$n$个数分布于$[1,2n]$中或者后$n$个数分布于$[n+1,3n]$中时需要的操作次数不超过2，个数为$,2 \times C_{2n}^{n} \times n! \times 2n! - \sum_{i = 0}^{n} C_{n}^{n - i} \times C_{n}^{i} \times C_{2n - i}^{n} \times n! \times n! \times n!$。
$f(p) \leq 3$，所有排列操作次数都不超过3，个数为$3n!$。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 3e6 + 117;
const int MAXM = 1e6 + 117;

int n, M;
LL a[MAXN];
LL inv[MAXN];//阶乘的逆元
LL fact[MAXN];//阶乘
LL fast_power(LL a, LL n, LL p) {
    LL ans = 1;
    a %= p;
    while(n) {
        if(n & 1) ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}
void init() {
    fact[0] = 1;
    for(int i = 1; i <= 3 * n; i++) {
        fact[i] = fact[i - 1] * i % M;
    }

    inv[3 * n] = fast_power(fact[3 * n], M - 2, M);
    for (int i = 3 * n - 1; i >= 0; i--) {
        inv[i] = inv[i + 1] * (i + 1) % M;
    }
}
LL sub(LL x, LL y) {
    return ((x - y) % M + M) % M;
}
LL com(int n, int m) {
    return fact[n] * inv[m] % M * inv[n - m] % M;
}
void solve() {
    a[0] = 1;
    a[1] =  sub(2 * fact[2 * n], fact[n]);
    a[2] = 2 * com(2 * n, n) % M * fact[n] % M * fact[2 * n] % M;
    for(int i = 0; i <= n; i++) {
        LL num = com(n, n - i) * com(n, i) % M * com(2 * n - i, n) % M;
        num = num * fact[n] % M * fact[n] % M * fact[n] % M;
        a[2] = sub(a[2], num);
    }
    a[3] = fact[3 * n];

    LL ans = 0;
    for(int i = 3; i > 0; i--) a[i] = sub(a[i], a[i - 1]);
    for(int i = 0; i <= 3; i++) ans = (ans + a[i] * i) % M;
    printf("%lld\n", ans);
}
int main() {
    scanf("%d%d", &n, &M);
    init();
    solve();
    return 0;
}

F. Wonderful Jump

题意：给定一个长度为$n$的正整数数组，每一次操作可以花费$\min(a_j \ldots a_i) \cdot (i - j)^2$的代价从$i \rightarrow j$。求从1到达每个位置的最小代价。

解法：可以非常容易的得到一个$\mathcal{O}(n^2)$的解决方案$dp_i = dp_j + \min(a_j \ldots a_i) \cdot (i - j)^2$。定义A是所有$a_i$的最大值。

如果$\min(a_j \ldots a_i) \cdot (i - j)^2 \gt A \cdot (i - j)^2$，这意味着执行$(i - j)$次变换比直接一次变换所需的代价更低。转换这个不等式可以得到$j - i > \frac{A}{\min(a_i \ldots a_j)}$，这意味着当区间的最小值变大时需要考虑的区间范围随之变小。
如果存在$j \lt k \lt i$且$\min(a_j \ldots a_i) = a_k$，则先$j \rightarrow k$再$k \rightarrow i$的方案优于$j \rightarrow i$。

$$ \min(a_j \ldots a_i) \cdot (i - j) ^ 2 > \min(a_j \ldots a_k) \cdot (k - j) ^ 2 + \min(a_k \ldots a_i) \cdot (i - k)^2\\a_k \cdot (i - j) ^ 2 > a_k \cdot (k - j) ^ 2 + a_k \cdot (i - k)^2\\(i - j) ^ 2 > (k - j) ^ 2 + (i - k)^2 $$

对此把需要考虑的情况分成两类

$\min(a_j \ldots a_i) = a_i$
- 如果$a_i \lt \sqrt{A}$，往前遍历直到$a_i$不是区间的最小值。
- 反之只需要往前遍历最多$\sqrt{A}$个元素即可。
$\min(a_j \ldots a_i) = a_j$
- 如果$a_j \lt \sqrt{A}$，维护一个单调栈使得栈中元素$a_j$都是区间$[j,i]$的最小值。
- 反之只需要往前遍历最多$\sqrt{A}$个元素即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, k = 635;
LL a[MAXN];
LL dp[MAXN];
void solve() {
    dp[0] = 0;
    vector<LL> st = {0};
    for(int i = 1; i < n; i++) {
        LL mi = a[i];
        for(int j = i - 1; j >= max(0, i - k); j--) {
            mi = min(mi, a[j]);
            dp[i] = min(dp[i], dp[j] + mi * (i - j) * (i - j));
        }

        //a[i]是最小值
        if(a[i] < k) {
            for(int j = i - 1; j >= 0; j--) {
                dp[i] = min(dp[i], dp[j] + a[i] * (i - j) * (i - j));
                if(a[j] <= a[i]) break;
            }
        }

        //a[j]是最小值
        for(int j : st) {
            dp[i] = min(dp[i], dp[j] + a[j] * (i - j) * (i - j));
        }
        if(a[i] < k) {
            while(!st.empty() && a[st.back()] >= a[i]) st.pop_back();
            st.push_back(i);
        }
    }
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        dp[i] = (LL)INF * INF;
    }
    solve();
    for(int i = 0; i < n; i++) printf("%lld ", dp[i]);
    return 0;
}

版权属于：小影
本文链接：http://kindkidll.com/index.php/archives/214/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

Last modification：February 16th, 2023 at 03:49 pm

如果觉得我的文章对你有用，请随意赞赏

Codeforces Round #842 (Div. 2)

我不会玩锐雯 • 2023 年 02 月 16 日

情况比赛链接：https://codeforces.com/contest/1768

A. Greatest Convex

题意：给定一个整数$k$，查找小于$k$的最大整数$x$，要求$x!+(x-1)!$是$k$的倍数。

解法： $(k-1)!+(k-2)! = (k-1) \times (k-2)!+(k-2)! = k \times (k-2)!$，答案始终为$k-1$。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
int n;
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        printf("%d\n", n - 1);
    }
    return 0;
}

B. Quick Sort

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
int n, k;
int a[MAXN];
void solve() {
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);

    int cnt = 0;//子序列长度
    for(int i = 0; i < n; i++) {
        if(a[i] == cnt + 1) cnt++;
    }

    int ans = (n - cnt + k - 1) / k;
    printf("%d\n", ans);
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

C. Elemental Decompress

题意：给定一个包含$n$个整数的数组$a$。需要求出两个全排列$p$和$q$满足$\max(p_i,q_i)=a_i$。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
int n;
struct node {
    int id;
    int x;
} a[MAXN];
bool f1[MAXN], f2[MAXN];
int ans1[MAXN], ans2[MAXN];
bool cmp(node a, node b) {
    return a.x < b.x;
}
bool cal() {
    int id1 = 1, id2 = 1;
    for(int i = 0; i <= n; i++) f1[i] = f2[i] = false;

    for(int i = 0; i < n; i++) {
        int target = a[i].x;
        if(!f1[target]) {//尝试放入p中
            while(id2 <= target && f2[id2]) {
                id2++;
            }
            if(id2 <= target) {
                ans1[a[i].id] = target;
                ans2[a[i].id] = id2;
                f1[target] = true;
                f2[id2] = true;
                continue;
            }
        }

        if(!f2[target]) {//尝试放入q中
            while(id1 <= target && f1[id1]) {
                id1++;
            }
            if(id1 <= target) {
                ans1[a[i].id] = id1;
                ans2[a[i].id] = target;
                f1[id1] = true;
                f2[target] = true;
                continue;
            }
        }

        return false;
    }
    return true;
}
void solve() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        a[i].id = i;
        scanf("%d", &a[i].x);
    }
    sort(a, a + n, cmp);

    if(cal()) {
        puts("YES");
        for(int i = 0; i < n; i++) printf("%d ", ans1[i]);
        putchar(10);
        for(int i = 0; i < n; i++) printf("%d ", ans2[i]);
        putchar(10);
        return;
    }
    puts("NO");
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

D. Lucky Permutation

题意：给定一个全排列，每次操作交换任意两个元素，问最少交换多少次使得排列逆序数恰好为1。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int T;
int n;
int a[MAXN];
int f[MAXN];
void dfs(int i, int root) {
    do {
        f[i] = root;
        i = a[i];
    } while(i != root);
}
void solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        f[i] = i;
    }

    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        if(f[i] == i) {//首次遍历环
            cnt++;
            dfs(i, i);
        }
    }

    for(int i = 1; i < n; i++) {
        if(f[i] == f[i + 1]) {//环中存在相邻的元素
            printf("%d\n", n - cnt - 1);
            return;
        }
    }

    printf("%d\n", n - cnt + 1); //环中没有相邻的元素
}
int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}

E. Partial Sorting

解法：注意到对于任意排列最多执行3次操作，可以把排列按操作次数的不同分别计数，然后分别计算对答案的贡献即可。

$f(p) = 0$，有且只有一个排列不需要操作，个数为$1$。
$f(p) \leq 1$，当前$n$个数已经升序或者后$n$个数已经升序时需要的操作次数不超过1，个数为$2 \times (2n!) - (n!)$。
$f(p) \leq 2$，当前$n$个数分布于$[1,2n]$中或者后$n$个数分布于$[n+1,3n]$中时需要的操作次数不超过2，个数为$,2 \times C_{2n}^{n} \times n! \times 2n! - \sum_{i = 0}^{n} C_{n}^{n - i} \times C_{n}^{i} \times C_{2n - i}^{n} \times n! \times n! \times n!$。
$f(p) \leq 3$，所有排列操作次数都不超过3，个数为$3n!$。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 3e6 + 117;
const int MAXM = 1e6 + 117;

int n, M;
LL a[MAXN];
LL inv[MAXN];//阶乘的逆元
LL fact[MAXN];//阶乘
LL fast_power(LL a, LL n, LL p) {
    LL ans = 1;
    a %= p;
    while(n) {
        if(n & 1) ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}
void init() {
    fact[0] = 1;
    for(int i = 1; i <= 3 * n; i++) {
        fact[i] = fact[i - 1] * i % M;
    }

    inv[3 * n] = fast_power(fact[3 * n], M - 2, M);
    for (int i = 3 * n - 1; i >= 0; i--) {
        inv[i] = inv[i + 1] * (i + 1) % M;
    }
}
LL sub(LL x, LL y) {
    return ((x - y) % M + M) % M;
}
LL com(int n, int m) {
    return fact[n] * inv[m] % M * inv[n - m] % M;
}
void solve() {
    a[0] = 1;
    a[1] =  sub(2 * fact[2 * n], fact[n]);
    a[2] = 2 * com(2 * n, n) % M * fact[n] % M * fact[2 * n] % M;
    for(int i = 0; i <= n; i++) {
        LL num = com(n, n - i) * com(n, i) % M * com(2 * n - i, n) % M;
        num = num * fact[n] % M * fact[n] % M * fact[n] % M;
        a[2] = sub(a[2], num);
    }
    a[3] = fact[3 * n];

    LL ans = 0;
    for(int i = 3; i > 0; i--) a[i] = sub(a[i], a[i - 1]);
    for(int i = 0; i <= 3; i++) ans = (ans + a[i] * i) % M;
    printf("%lld\n", ans);
}
int main() {
    scanf("%d%d", &n, &M);
    init();
    solve();
    return 0;
}

F. Wonderful Jump

题意：给定一个长度为$n$的正整数数组，每一次操作可以花费$\min(a_j \ldots a_i) \cdot (i - j)^2$的代价从$i \rightarrow j$。求从1到达每个位置的最小代价。

解法：可以非常容易的得到一个$\mathcal{O}(n^2)$的解决方案$dp_i = dp_j + \min(a_j \ldots a_i) \cdot (i - j)^2$。定义A是所有$a_i$的最大值。

如果$\min(a_j \ldots a_i) \cdot (i - j)^2 \gt A \cdot (i - j)^2$，这意味着执行$(i - j)$次变换比直接一次变换所需的代价更低。转换这个不等式可以得到$j - i > \frac{A}{\min(a_i \ldots a_j)}$，这意味着当区间的最小值变大时需要考虑的区间范围随之变小。
如果存在$j \lt k \lt i$且$\min(a_j \ldots a_i) = a_k$，则先$j \rightarrow k$再$k \rightarrow i$的方案优于$j \rightarrow i$。

对此把需要考虑的情况分成两类

$\min(a_j \ldots a_i) = a_i$
- 如果$a_i \lt \sqrt{A}$，往前遍历直到$a_i$不是区间的最小值。
- 反之只需要往前遍历最多$\sqrt{A}$个元素即可。
$\min(a_j \ldots a_i) = a_j$
- 如果$a_j \lt \sqrt{A}$，维护一个单调栈使得栈中元素$a_j$都是区间$[j,i]$的最小值。
- 反之只需要往前遍历最多$\sqrt{A}$个元素即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, k = 635;
LL a[MAXN];
LL dp[MAXN];
void solve() {
    dp[0] = 0;
    vector<LL> st = {0};
    for(int i = 1; i < n; i++) {
        LL mi = a[i];
        for(int j = i - 1; j >= max(0, i - k); j--) {
            mi = min(mi, a[j]);
            dp[i] = min(dp[i], dp[j] + mi * (i - j) * (i - j));
        }

        //a[i]是最小值
        if(a[i] < k) {
            for(int j = i - 1; j >= 0; j--) {
                dp[i] = min(dp[i], dp[j] + a[i] * (i - j) * (i - j));
                if(a[j] <= a[i]) break;
            }
        }

        //a[j]是最小值
        for(int j : st) {
            dp[i] = min(dp[i], dp[j] + a[j] * (i - j) * (i - j));
        }
        if(a[i] < k) {
            while(!st.empty() && a[st.back()] >= a[i]) st.pop_back();
            st.push_back(i);
        }
    }
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        dp[i] = (LL)INF * INF;
    }
    solve();
    for(int i = 0; i < n; i++) printf("%lld ", dp[i]);
    return 0;
}

版权属于：小影
本文链接：http://kindkidll.com/index.php/archives/214/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

Codeforces Round #842 (Div. 2)

A. Greatest Convex

B. Quick Sort

C. Elemental Decompress

D. Lucky Permutation

E. Partial Sorting

F. Wonderful Jump

Leave a Comment Cancel reply

【每日一题】4月7日树

链式前向星

handsome主题修改记录

红黑树入门

【每日一题】4月2日月月查华华的手机

Codeforces Round #811 (Div. 3)

【每日一题】4月3日 Shortest Path

SOS DP

2021牛客寒假算法基础集训营1

快速幂

Codeforces Round #842 (Div. 2)

A. Greatest Convex

B. Quick Sort

C. Elemental Decompress

D. Lucky Permutation

E. Partial Sorting

F. Wonderful Jump