ICPC North Central NA Contest 2017 - D. Smooth Array 分组背包+前缀最大值转移

357 浏览 0 回复 2020-03-02

工大最菜

+关注

题目链接：https://nanti.jisuanke.com/t/43371
题目大意：有n个数。给你一个k和s。每个数字可以改变成0-s。让你以相邻的k个为一组[a[1]…a[k]], [a[2]…a[k+1]]…。问使每一组的和为s。至少需要改变多少个数。

根据题目的条件这个数组最后的样子一定是以k为循环节。a[1]=a[k+1],a[2]=a[k+2]…

那么就是有k组数。我们把每组数出现的次数计为：size。那么就可以变成一个容量为S的分组背包。出现的数组体积为数字。贡献为size（如果把这组都变成这个数字，那么这组可以不用改变的数字个数）。
最后n-f[n][s]就是答案。

$转移方程：如果 x 在这组出现过 : f [i] [s] = m a x (f [i] [s - x], f [i] [j] + s i z e [i] [x])$ $如果 x 在这组没有出现过 : f [i] [s] = m a x (f [i - 1] [s - x], f [i] [j])$

如果我们枚举X。复杂度就是 $O (K * S * S)$ 是不可以的。

$如果 x 在这组没有出现过 : f [i] [s] = m a x (f [i - 1] [s - x], f [i] [j]) 就是 f [i - 1] [s] 的前缀最大值。我们处理一下，就可以只枚举出现过的数字$
$长度为 n 有 k 组。每组有 n / k 个。时间复杂度 : O (K * S * (N / K)) = O (S * N)$

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int a[5005];
int siz[5005][5005];
vector<int> v[5005];
int f[5005][5005];
int g[5005][5005];
int main(){

    int n, k, s;scanf("%d%d%d", &n, &k, &s);
    for(int i=0; i<n; i++){
        scanf("%d", &a[i]);
        if(siz[i%k+1][a[i]]==0){
            v[i%k+1].push_back(a[i]);
        }
        siz[i%k+1][a[i]]++;
    }
    for(int i=1; i<=s; i++){
        f[0][i]=-1<<30;
    }

    f[0][0]=0;
    for(int i=1; i<=k; i++){

        for(int j=0; j<=s; j++){
            g[i][j]=g[i-1][j];
        }
        for(int j=0; j<=s; j++){
            g[i][j]=max(j?g[i][j-1]:0, f[i-1][j]);
        }

        for(int j=0; j<=s; j++){

            //f[i][j]=f[i-1][j]+siz[i][0];
            for(int k=0; k<v[i].size(); k++){
                if(j>=v[i][k]){
                    f[i][j]=max(f[i][j], f[i-1][j-v[i][k]]+siz[i][v[i][k]]);
                }
                else{
                    f[i][j]=max(f[i][j], f[i-1][j]);
                }
            }
        }

        for(int j=0; j<=s; j++){
            f[i][j]=max(f[i][j], g[i][j]);
        }
    }
    cout<<n-f[k][s]<<endl;

    return 0;
}