[Day6]B 君的第三题 (shenyang)

题目大意

给你一个长度为n的数组，你需要更改里面各项的值使得它们两两互质。
代价为改后数字与原始值的差值的绝对值。求最小代价。

题解

这个题解算是在分享做题的心路历程，比较磨叽，可以只看黑体字部分

一开始都已经弃疗了（别一开始就放弃啊喂!）准备打一个暴力骗点分……
于是就打算枚举每一项，对于每一项枚举每一个可能值。
枚举值肯定有范围的，不能可在int范围内枚举吧。
于是就发现了：
结论1：改后的数的范围在[1,59]之间
下界是题目给的，我们只对上界进行讨论
证明：我们设数列为 $A_1,A_2,\cdots A_n$ ，由于题目中 $A_i\le30$ ，且1与任意自然数互质。因此 $|A_i-1|\le|A_i-59|$ 且 $|A_i-1|<|A_i-59|$ 。因此改后的数的上界为59。

找到了范围就可以开心地枚举啦！！理论上 $O(59^n)$ n=4的时候过不了。但实际上可以很多情况下可以提前判断不互质而提前退出，因此30pt到手！

很自然地去想如何判断不互质——有相同的质因子

每次都去算质因子好麻烦，而且数字很小，于是就可以开一个数组 $zz[i]$ 存i的质因子，我们发现60以内的质数只有17个，可以直接用状态存

都写到这了还写什么暴力orz，直接上状压啊！

状态设计↓
我们设计 $d[i][j]$ 表示第i个数，在状态j（有多少个质因子）下，所耗费的最小费用。
初始化d数组为 $\infty$ ，d[0][0]=0
现在需要枚举每个可以转移的合法状态，设初始时 $fzz=((1<<17)-1)\ xor\ zz[j]$ ，该项原始值为a
状态转移方程为：
$d[i][fzz|zz[j]]=min(d[i-1][fzz]+abs(a-j))$
最后 $min(d[n][i])$ 就是答案

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=110;
int d[MAXN][1<<17];

int p[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};

int pre(int x){
    int s=0;
    for(int i=0;i<17;++i)
        if(x%p[i]==0)
            s|=(1<<i);
    return s;
}
int zz[60];

int main(){
    memset(d,0x3f,sizeof(d));
    d[0][0]=0;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=59;++i){//预处理出质因子
        zz[i]=pre(i);
    }

    for(int i=1;i<=n;++i){
        int a;scanf("%d",&a);
        for(int j=1;j<=59;++j){
            int fzz=((1<<17)-1)^zz[j];
            for(int k=fzz;;(--k)&=fzz){//枚举每一个合法状态，也就是枚举该状态原本为1位置的变成0
                d[i][k|zz[j]]=min(d[i][k|zz[j]],d[i-1][k]+abs(a-j));
                if(k==0)
                    break;
            }
        }
    }
    int ans=1<<30;
    for(int i=0;i<=(1<<17)-1;++i)
        ans=min(ans,d[n][i]);
    printf("%d\n",ans);
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int MAXN=110;

int d[MAXN][1<<17];

int p[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};

int pre(int x){

int s=0;

for(int i=0;i<17;++i)

if(x%p[i]==0)

s|=(1<<i);

return s;

}

int zz[60];

int main(){

memset(d,0x3f,sizeof(d));

d[0][0]=0;

int n;

scanf("%d",&n);

for(int i=1;i<=59;++i){//预处理出质因子

zz[i]=pre(i);

}

for(int i=1;i<=n;++i){

int a;scanf("%d",&a);

for(int j=1;j<=59;++j){

int fzz=((1<<17)-1)^zz[j];

for(int k=fzz;;(--k)&=fzz){//枚举每一个合法状态，也就是枚举该状态原本为1位置的变成0

d[i][k|zz[j]]=min(d[i][k|zz[j]],d[i-1][k]+abs(a-j));

if(k==0)

break;

}

int ans=1<<30;

for(int i=0;i<=(1<<17)-1;++i)

ans=min(ans,d[n][i]);

printf("%d\n",ans);

return 0;

}

题目大意

题解

代码

发送评论 编辑评论

发送评论编辑评论