首页 > 代码库 > codeforces 453 B Little Pony and Harmony Chest (状压dp)
codeforces 453 B Little Pony and Harmony Chest (状压dp)
题目大意:
需要你构造一个b数组。使得b数组中的所有元素互质。
而且使得b数组与a数组中的每个对应下标元素的差值和最小。
思路分析:
考虑到 a中所有元素都是 0 - 30.
所以b中的元素也只可能在 0 - 59.
因为如果b 选择60的话,结果和1是一样的,而且b序列中 1 可以重复出现很多次。
因为gcd (1,x) = 1。。
所以们首先把2 - 59中的所有素数处理出来,只有17个。
然后状压这些素数因子。
dp[i] [s] [0] 表示 递推到第 i 个位置 达到素数因子为s的状态下,第 i 个位置放的数。
dp[i] [s] [1] 表示。。。。。。。。。。。。。。。。。。。。。的最小值。
dp[i] [s] [2] 表示。。。。。。。。。。。。。。。。。。。。。的前驱,方便输出方案。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; int prime[20]; bool isprime(int x) { for(int i=2;i<x;i++) if(x%i==0)return false; return true; } int dp[105][1<<17][3]; int n; int a[105]; int Abs(int x) { return x>0?x:-x; } void print(int dep,int x) { if(dep==0)return; print(dep-1,dp[dep][x][0]); printf("%d ",dp[dep][x][2]); } int main() { int cnt=0; for(int i=2;i<=59;i++) if(isprime(i))prime[cnt++]=i; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int s; memset(dp,0x3f,sizeof dp); for(int i=0;i<(1<<17);i++)dp[0][i][0]=dp[0][i][1]=dp[0][i][2] = 0; for(int i=1;i<=n;i++) { for(int j=1;j<=59;j++) { s=0; for(int k=0;k<cnt;k++) { if(j%prime[k]==0) s|=(1<<k); } for(int st=1;st<(1<<17);st++) { if(!(st&s)) { if(dp[i-1][st][1]+Abs(a[i]-j)<dp[i][st|s][1]) { dp[i][st|s][2]=j; dp[i][st|s][1]=dp[i-1][st][1]+Abs(a[i]-j); dp[i][st|s][0]=st; } } } } } int ans=0x3f3f3f3f; int pos=0; for(int i=0;i<(1<<17);i++) { if(dp[n][i][1]<ans) { ans=dp[n][i][1]; pos=i; } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。