Kitchen Knobs

首先，一个 trivial 的想法是，因为每个旋钮如果上面的数字并非全部相同则其必有唯一最优位置，故直接扔掉那些全部相同的旋钮，对于剩余的求出其最优位置。明显此位置是一 \(0\sim6\) 的数。

因为是区间同时旋转，所以转成数之后就是区间加同一个数。

一个经典套路是差分。这样就变成了每次同时修改序列中的两个数，一个加 \(x\)，另一个减 \(x\)。当然，还可以只修改一个位置到任意值。

然后我们发现，对于一些和为 7 的倍数的数，我们只需要这些数的总数 \(-1\) 次“修改两个数”即可处理它们。

然后我们又发现，首先那些本身就是 0 的数可以直接扔掉，再怎么搞都不会修改到它们；这样的话，每次合并所能省下的次数最多只是 \(50\%\)，因此我们一定会合并那些 \(50\%\) 的方案，即合并 \((1,6),(2,5),(3,4)\)。

这样合并完后，我们发现最多只剩下 3 种不同的数，因此一个 \(n^3\) 的 DP 就可以构思出来了。

然后我们还需要知道所有的和为 7 的组合。并且，这些组合必须是极小组合。于是我们直接 \(7^3\) 枚举三个数的次数，再 \(7^3\) 枚举其子集验证其是否是极小组合即可。

最后别忘记算 \((7,0,0),(0,7,0),(0,0,7)\) 这三种组合！！！因为没有考虑到这个我挂了很久。

这样一通算下来，极小组合数可以被视作很小的常数。于是直接 \(n^3\) 的 DP 即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,cmp,res,cnt;
int a[N],f[N][N][N],g[N][4],tot[8],lim[4],num[4];
string s,t;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
		t=s;
        bool as=true;
        for(int j=1;j<7;j++) if(s[j]!=s[0]){as=false;break;}
        if(as){
			i--;
			n--;
			continue;
		}
        for(int j=0;j<7;j++){
			rotate(s.begin(),s.begin()+1,s.end());
			t=max(t,s);
		}
        for(int j=0;j<7;j++){
            if(s==t){
				a[i]=j;
				break;
			}
            rotate(s.begin(),s.begin()+1,s.end());
        }
    }
    n++;
    for(int i=n;i>=2;i--) a[i]=(a[i]-a[i-1]+7)%7;
    for(int i=1;i<=n;i++) tot[a[i]]++;
    for(int i=1,x;i<=3;i++){
		x=min(tot[i],tot[7-i]);
		tot[i]-=x;
		tot[7-i]-=x;
		n-=x;
	}
    n-=tot[0];
    for(int i=1;i<7;i++){
		if(tot[i]){
			lim[cmp]=tot[i];
			num[cmp]=i;
			cmp++;
		}
	}
    for(int i=0;i<7;i++){
		for(int j=0;j<7;j++){
			for(int k=0;k<7;k++){
				if((i*num[0]+j*num[1]+k*num[2])%7) continue;
				if(!i&&!j&&!k) continue;
				bool ok=true;
				for(int I=0;I<=i;I++){
					for(int J=0;J<=j;J++){
						for(int K=0;K<=k;K++){
							if((I*num[0]+J*num[1]+K*num[2])%7) continue;
							if((!I&&!J&&!K)||(i==I&&j==J&&k==K)) continue;
							ok=false;break;
						}
					}
				}
				if(ok){
					g[cnt][0]=i;
					g[cnt][1]=j;
					g[cnt][2]=k;
					cnt++;
				}
			}
		}
	}
    g[cnt][0]=7;g[cnt][1]=0;g[cnt][2]=0;cnt++;
    g[cnt][0]=0;g[cnt][1]=7;g[cnt][2]=0;cnt++;
    g[cnt][0]=0;g[cnt][1]=0;g[cnt][2]=7;cnt++;
    for(int i=0;i<=lim[0];i++){
		for(int j=0;j<=lim[1];j++){
			for(int k=0;k<=lim[2];k++){
				for(int l=0;l<cnt;l++){
					if(i<g[l][0]||j<g[l][1]||k<g[l][2]) continue;
					f[i][j][k]=max(f[i][j][k],f[i-g[l][0]][j-g[l][1]][k-g[l][2]]+1);
				}
				res=max(res,f[i][j][k]);
			}
		}
	}
    cout<<n-res;
    return 0;
}