P4749 【CERC2017】Kitchen Knobs

· · 题解

P4749 Kitchen Knobs

记录每个字符串以第 i 个位置开头得到的数最大，题意转换为，对 n 个值域为 [0,6] 的数在 \mod 7 意义下区间加或减，求使 n 个数都变成 0 的最小操作次数。

先差分，操作就变成了选两个位置 +x，-x（即 +(7-x) ），或者选一个位置 +x (区间一直加到末尾)，每个位置的值都变成 0 时完成任务，现在对于所有数字的操作就与位置无关了。

如果只选一个位置，可以直接加减变成 0 ，还要使操作次数尽量少，就要尽量做到一次操作配对两个，使他们同时变成 0 ，就可以少操作一次。

首先可以把 1 和 6 , 2 和 5 , 3 和 4 三组数字配对。

这样操作后最多三组中各剩下一种数字，考虑对这三种数字的配对方法dp。

记 f[i][j][k] 表示分别选了 i ，j，k 个第一，二，三种数，能够配对消去的最大组数。

每次选择加入一个数，如果当前三种数分别乘上选择数量再相加得到的和为 7 的倍数，就一定再能配出正好两个消为 0 的对。

例如：

选的数是：2 2 3
step1: 0 4 3
step2: 0 0 0
比一个个消少了一步

最后答案为 n - 匹配对数

复杂度 O(N^3) ，而且跑不满

另外要注意，原字符串每位都相同时，怎么转都是一样的，它的值随意，不用变成 0 ，不然操作次数会变多，所以要剔除它。洛谷的数据似乎水了，我开始没写这部分但没查出来。

#include<iostream>
#include<stdio.h>
using namespace std;
short f[502][502][502];
int cnt[5],n,m,num[7],st[502],rst[5];
char c[10];
bool cmp(int x,int y){
    for(int i=x,j=y,k=0;k<7;k++,i=(i+1)%7,j=(j+1)%7){
        if(c[i]>c[j]) return 0;
        if(c[i]<c[j]) return 1;
    }
    return 0;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",c);
        bool flag=1;
        for(int j=1;j<7;j++){
            if(c[j]!=c[j-1]){
                flag=0;break;
            }
        }
        if(flag) continue;//每位相同，怎么转都行，没有差分数组的限制 
        int mx=0;
        for(int j=1;j<7;j++){
            if(cmp(mx,j)){
                mx=j;
            }
        }
        st[++m]=mx;
    }
    for(int i=1;i<=m;i++){
        num[(st[i]-st[i-1]+7)%7]++;
    }
    int ans=0;
    for(int i=1;i<=3;i++){
        if(num[i]<num[7-i]){
            ans+=num[i];
            rst[i]=7-i;
            cnt[i]=num[7-i]-num[i];
        }
        else{
            ans+=num[7-i];
            rst[i]=i;
            cnt[i]=num[i]-num[7-i];
        }
    }
    int sum=cnt[1]+cnt[2]+cnt[3];
    for(int i=0;i<=cnt[1];i++){
        for(int j=0;j<=cnt[2];j++){
            for(int k=0;k<=cnt[3];k++){
                if(i) f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);
                if(j) f[i][j][k]=max(f[i][j][k],f[i][j-1][k]);
                if(k) f[i][j][k]=max(f[i][j][k],f[i][j][k-1]);
                if((i*rst[1]+j*rst[2]+k*rst[3])%7==0&&(i+j+k>0)){
                    f[i][j][k]++;
                }
            }
        }
    }
    ans+=sum-f[cnt[1]][cnt[2]][cnt[3]];
    printf("%d\n",ans);
    return 0;
}