[CERC2017]Kitchen Knobs

· · 题解

一道比较巧妙的思维题.

转化后题意:给你一个数组,每次可以将a[i],i\in[l,r]变成(a[i]+v)\%7,i\in[l,r],v\in[1,6].求使得整个数组变为0的最小操作次数.

这个题一看就非常差分,所以我们先差分一下.发现操作变成了,对于差分数组c[i]你可以将c[i]+v,(c[j]-v+7)\%7,i<j或者只将c[i]+v.

就相当于我们将所有c[i]分组,使得同一组的sum\%7=0(这样同一组就可以用sz-1此组全部弄成0)并且组数尽可能多.

乍一看好像没啥特别的,但是我们发现0是不用操作的,16,25,34,两两配对分组是很优秀的.而且配对过后,我们就只剩下3种数了.

我们此时将剩下的数设一个四维f[i][j][k] 表示,选了i个第一种数,j个第二种数,k个第三种数,我们发现当i* v[1]+j* v[2]+k* v[3]=0时,我们此时组数就可以加一,因为我们此时必然可以通过i,j,k的一些组合凑出一组新的sum为0,转移就是你枚举一个数添加就行了.但n^3的空间太大了开不下,我们可以滚动数组或者short解决问题.

注意你转化的时候,如果那个数字全部相同,那它是没有意义的(咋转都没区别),一定要记得特判这种情况!!!(考场上感觉很难想到这种情况)

转化就是你枚举一下顺时针转几次得到最大值,那个次数就是题目中的a_i了

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
const int N=514;
int n,nw,as,mx[N],a[N][8],p[10],c[10],ct[10];
short f[N][N][N];
void MX(short &a,short b){a=a>b?a:b;}
int main(){
    scanf("%d",&n);
    rep(i,1,n){scanf("%d",&a[i][0]);
        if(a[i][0]%1111111==0){i--;n--;continue;}//一定要判,巨坑
        rep(j,1,6){
            a[i][j]=(a[i][j-1]%1000000)*10+a[i][j-1]/1000000;
            if(a[i][mx[i]]<a[i][j])mx[i]=j;
        }
    }//转化mx[i]相当于a[i]
   rep(i,1,n)ct[(mx[i]-mx[i-1]+7)%7]++;
    p[1]=abs(ct[1]-ct[6]);c[1]=ct[1]>ct[6]?1:6;
    p[2]=abs(ct[2]-ct[5]);c[2]=ct[2]>ct[5]?2:5;
    p[3]=abs(ct[3]-ct[4]);c[3]=ct[3]>ct[4]?3:4;//将16,25,34先行配对,0不用管
    as+=max(ct[1],ct[6])+max(ct[2],ct[5])+max(ct[3],ct[4]);
    rep(i,0,p[1])rep(j,0,p[2])rep(k,0,p[3]){
        f[i][j][k]+=(i*c[1]+j*c[2]+k*c[3])%7==0;//这样就可以形成一个新的分组
        MX(f[i+1][j][k],f[i][j][k]);
        MX(f[i][j+1][k],f[i][j][k]);
        MX(f[i][j][k+1],f[i][j][k]);//依次枚举数添加
    }
   printf("%d",as+1-f[p[1]][p[2]][p[3]]);
}