Link

ARC166 B Make Multiples

Question

给出 \(N\) 个整数， \(A_1...A_N\) ，还有三个数 \(a,b,c\)

我们可以给 \(A_i\) 加上 \(1\)

需要使得数组 \(A\) 满足，存在一个数是 \(a\) 的倍数，一个数是 \(b\) 的倍数，一个数是 \(c\) 的倍数

求最少的操作次数

Solution

考虑对于每个数的操作无非就这几种

不变
加成 \(a\) 的倍数
加成 \(b\) 的倍数
加成 \(c\) 的倍数
加成 \(lcm(a,b)\) 的倍数
加成 \(lcm(a,c)\) 的倍数
加成 \(lcm(b,c)\) 的倍数
加成 \(lcm(a,b,c)\) 的倍数

我们不知道每个数具体的操作，但发现操作数很少，就考虑状态压缩

用 \(a\) 表示二进制的第一位，用 \(b\) 表示二进制的第二位，用 \(c\) 表示二进制的第三位

我们可以用二进制表示状态和操作

那么上面的8种操作就可以用 1-7 来表示

定义 \(F[i][s]\) 表示前 \(i\) 个整数，此时的状态是 \(s\) 的最小的加的次数

转移方程：

\[F[i][s|s'] = min(F[i][s] + w[s']) \]

答案 \(F[N][7]\)

Code

#include<bits/stdc++.h>
#define int __int128
using namespace std;
const int maxn= 200005;
inline int read(){
    int ret = 0, f = 1;char ch = getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f = -f;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+ch-48,ch=getchar();
    return ret;
}
inline void print(int x, int flag = 1)
{
    if (x < 0) putchar('-'), x = ~(x - 1);
    if (x > 9) print(x / 10, 0);
    putchar(x % 10 + 48);
    if (flag) putchar(flag & 1 ? ' ' : '\n');
}
inline int gcd(int x,int y) {return y?gcd(y,x%y):x;}
inline int lcm(int x,int y) {return x/gcd(x,y) *y;}
int N,x,y,z,F[maxn][8],tmp[8],w[8];
signed main(){
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
    N=read();x=read();y=read();z=read();
    w[1]=x;w[2]=y;w[4]=z;w[3]=lcm(x,y);w[5]=lcm(x,z);w[6]=lcm(y,z);w[7]=lcm(x,lcm(y,z));
    memset(F,0x7f,sizeof F);F[0][0]=0;
    for(int i=1;i<=N;i++){
        int now=read();
        for(int j=1;j<8;j++)
            tmp[j]=(w[j]-(now%w[j]))%w[j];
        F[i][0]=0;
        for(int j=0;j<8;j++){
            F[i][j]=min(F[i][j],F[i-1][j]);
            for(int k=1;k<8;k++)
                F[i][j|k]=min(F[i][j|k],F[i-1][j]+tmp[k]);
        }
    }
    print(F[N][7]);
    return 0;
}