自动搬运

查看原文

来自洛谷，原作者为

	弦巻こころ 放置型音游玩家

搬运于2025-08-24 22:03:13，当前版本为作者最后更新于2021-05-21 21:00:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道比较巧妙的思维题.

转化后题意:给你一个数组,每次可以将$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]]);
}