最大区间和变形

题意：可以选择操作一串区间，将区间内的某一个数全部变成一个新的数字，询问整个区间中某个数字的出现次数总共有多少个？

思路分析：首先最后选的一定是一个区间，然后 ans = cnt(1, l-1, c)+cnt(r+1, n, c)+cnt(l, r, d)

　　　　　　　　　　　　　　　　　　　　　　ans = cnt(1, n, c) - cnt(l, r, c) + cnt(l, r, d)

　　　　　　即，我们只需要最大化 l - r 内的 d - c 的个数，其实就是个最大区间和的变化版本，统计一个数时，当这个数的的个数小于C的个数时，只需要将它的个数更新到和 d 的个数一样即可

代码示例：

int n, c;

int a[maxn];

int cnt[maxn];

void solve(){

    int f = 0;

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

        cnt[a[i]] = max(cnt[a[i]], cnt[c]);

        cnt[a[i]]++;

        f = max(f, cnt[a[i]]-cnt[c]);

    }

    printf("%d\n", f+cnt[c]);

}

int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    cin >> n >> c;

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

    solve();

    return 0;

}

巴特西

最大区间和变形 - codeforces

最新文章

热门文章