【2020NOI.AC省选模拟#5】C. 光滑序列

题目链接

原题解：

光滑的序列一定有长度为$K$的循环节。

使用动态规划，设$F(i,j)$为使前$i$个整数的和为$j$的最小修改次数。

记$cost(i,v)$为令$A_i,A_{i+K},A_{i+2K},\cdots$等于$v$需要而修改次数。则$F(i,j)=\min\limits_v \{F(i-1,j-v)+cost(i,v)\}$。

可以发现，$A_i,A_{i+K},A_{i+2K},\cdots$中至多有$O(\dfrac{N}{K})$个不同的值。

我们可以先用$F(i,j)=\min \limits_v \{F(i-1,j-v)+\left\lfloor \dfrac{N-i}{K} \right\rfloor +1\}$一次性转移没有在这些位置中出现过的$v$，然后再对这$O(\dfrac{N}{K})$个$v$单独转移。

复杂度为$O(KS\times \dfrac{N}{K})=O(NS)$。

补充：

$O(N^2)$比$O(N^3)$改进的地方是两点：

• 使用$f(i-1,j)$的前缀最小值来设定$f(i,j)$的初值。
• 枚举增加的数进行转移，于是可以判断这种数存不存在，进而减少无效转移。因为模$K$相同的位置只有$O(\dfrac{N}{K})$个，所以复杂度就对了。

代码（100分）：

#include
#include
#include
#include
#include
#define IL inline
#define RG register
using namespace std;
#define RI RG int
#define RC RG char
const int N=5000;
    
    int n,k,s,a[N+3];
    int b[N+3][N+3],c[N+3];
    int f[N+3][N+3];

int main(){
    scanf("%d%d%d",&n,&k,&s);
    for(RI i=1;i<=n;i++)
        scanf("%d",&a[i]);
    
    for(RI i=1,t=1;i<=n;i++,t+1>k?t=1:t++){
        b[t][a[i]]++;
        c[t]++;
        
    }
    
    for(RI i=1;i<=s;i++)
        f[0][i]=n+1;
    f[0][0]=0;
    for(RI i=1;i<=k;i++){
        for(RI j=0,x=f[i-1][0];j<=s;j++){
            x=min(x,f[i-1][j]);
            f[i][j]=x+c[i];
            
        }
        
        for(RI j=0;j<=s;j++)
        if(b[i][j])
            for(RI p=j;p<=s;p++)
                f[i][p]=min(f[i][p],f[i-1][p-j]+c[i]-b[i][j]);
        
    }
    
    printf("%d",f[k][s]);

    return 0;

}