Codeforces 958C3 - Encryption (hard)

C3 - Encryption (hard)

思路：

记sum[i]表示0 - i 的和对 p 取模的值。

1.如果k * p > n，那么与C2的做法一致，O(k*p*n)复杂度低于1e8。

2.如果k * p <= n

那么根据抽屉原理，必有k个sum[i]相同，

那么任意取k - 1个相同的 sum[i]，记它们的下标为 l₁，l₂，......，l_k-1，那么显然区间[l_i+ 1, l_i+1]（1<=i<k-1）的贡献为0

有贡献的区间只有[1,l₁]和[l_k-1+ 1,n]由于两个区间的贡献加起来小于2 * (p - 1) ，所以最后的答案要么为 sum[n]，要么为 sum[n] + p

那么怎么判断是前者还是后者呢？

只要判断在sum中能不能找到一个以sum[n]结尾的长度为k的非严格上升子序列就可以了

如果能找到就是sum[n]，否则就是 sum[n] + p

LIS的复杂度O(nlogn)

代码：

#include<bits/stdc++.h>

using namespace std;

#define LL long long

#define pb push_back

#define mem(a, b) memset(a, b, sizeof(a))

const int N = 5e5 + ;

const int INF = 0x3f3f3f3f;

int a[N];

int dp[][];

int _dp[N];

int main() {

    int n, k, p;

    scanf("%d%d%d", &n, &k, &p);

    for (int i = ; i <= n; i++) scanf("%d", &a[i]),a[i] += a[i-], a[i] %= p;

    if (k * p > n) {

        mem(dp, INF);

        dp[][] = ;

        for (int i = ; i <= n; i++) {

            for (int j = k; j >= ; j--) {

                for (int l = ; l < p; l++){

                    dp[a[i]][j] = min(dp[a[i]][j], dp[l][j-] + ((a[i] - l)%p+p)%p);

                }

            }

        }

        printf("%d\n", dp[a[n]][k]);

    }

    else {

        mem(_dp, INF);

        for (int i = ; i <= n - ; i++) {

            *upper_bound(_dp + , _dp + n, a[i]) = a[i];

        }

        if(_dp[k - ] <= a[n]) printf("%d\n", a[n]);

        else printf("%d\n", a[n] + p);

    }

    return ;

}

巴特西

Codeforces 958C3 - Encryption (hard)

最新文章

热门文章