题解：P4749 [CERC2017] Kitchen Knobs

· · 题解

简要题意

有 n 个手柄，手柄上有 7 个数字围成一圈，手柄的大小为顶端开始顺时针读取数字，每次选择一个区间，将区间内的手柄向同一方向转动相同的次数。求最少的步数使所有的炉子都设定到可能的最大火力 。

主要算法

dp，差分。

主要思路

题目转化 1：反向考虑，预处理出每个手柄的最大值的位置，记录每个位置的转动次数，每次操作就是区间加，只要最后每个位置的值模 p 等于 0 即可（相当于从目标通过转动转回初始状态。

题目转化 2：只有区间加，可以通过查分，将区间加转化为两个单点修改。只要差分数组都为 0，原数组就满足条件。

题目转化 3：仍然不好做，发现对于一些和为 7 的倍数的数，我们只需要这些数的总数 −1 次“修改两个数”即可处理它们。所以最终答案为（k 为和为 7 的倍数的数集的个数）。

\sum_{i=1}^{k}cnt_{i}-1=n-k

dp 方程：dp_{a_0,a_1,a_2,a_3,a_4,a_5,a_6} 表示 a_0 个 0，a_1 个 1，a_2 个 2 可以分成最多多少个部分。显然 O(n^6) 已经炸了。

dp 优化：0 明显不用考虑，同时将尽可能多的 1 和 6，2 和 5，3 和 4 分在一起。这样将其中一个用完，就只剩 3 个数了，O(n^3) 显然可以。

dp 转移：考虑加一个元素不增加部份数 ，所以将 dp_{a_1,a_2,a_3} 向 dp_{a_1+1,a_2,a_3}，dp_{a_1,a_2+1,a_3}，dp_{a_1,a_2,a_3+1} 转移。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=510;
#define int long long
int n,ans,wz[10],col[10],b[N],cnt[10],mx[N];
short f[N][N][N];
signed main()
{
//  ios::sync_with_stdio(0);
//  cin.tie(0),cout.tie(0); 
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        bool flag=1;
        cin>>wz[0];
        if(wz[0]%1111111==0)
        {
            i--,n--;
            continue;
        }
        for(int j=1;j<=6;j++)
        {
            wz[j]=(wz[j-1]%1000000)*10+wz[j-1]/1000000;
            if(wz[j]>wz[mx[i]])mx[i]=j;
        }
    }
    for(int i=1;i<=n;i++)cnt[(mx[i]-mx[i-1]+7)%7]++;
//  for(int i=1;i<=6;i++)cout<<cnt[i]<<' '; 
    ans+=max(cnt[1],cnt[6])+max(cnt[2],cnt[5])+max(cnt[3],cnt[4]);
    col[1]=cnt[1]>cnt[6]?1:6;col[2]=cnt[2]>cnt[5]?2:5;col[3]=cnt[3]>cnt[4]?3:4;
    cnt[3]=abs(cnt[3]-cnt[4]);cnt[1]=abs(cnt[1]-cnt[6]);cnt[2]=abs(cnt[2]-cnt[5]);
    for(int a1=0;a1<=cnt[1];a1++)
        for(int a2=0;a2<=cnt[2];a2++)
            for(int a3=0;a3<=cnt[3];a3++)
            {
                f[a1][a2][a3]+=(a3*col[3]+a2*col[2]+a1*col[1])%7==0;
                f[a1+1][a2][a3]=max(f[a1+1][a2][a3],f[a1][a2][a3]);
                f[a1][a2+1][a3]=max(f[a1][a2+1][a3],f[a1][a2][a3]);
                f[a1][a2][a3+1]=max(f[a1][a2][a3+1],f[a1][a2][a3]);             
            }

    printf("%lld\n",ans+1-f[cnt[1]][cnt[2]][cnt[3]]);
    return 0;
}

注意事项

如果所有数相同则没有最优位置，直接不管就行了。