codeforces 454 D. Little Pony and Harmony Chest(状压dp)

题目链接:http://codeforces.com/contest/454/problem/D

题意:给定一个序列a, 求一序列b,要求∑|ai−bi|最小。并且b中任意两数的最大公约数为1.

题解:首先要满足最大公约数为1只要控制b中的最小素因数就行。由于a最大之后30,所以加的数肯定不会超过60

如果超过了,直接选择1更小,然后1~60内最多只有17个素数,所以最多状态就是1<<17于是可以考虑一下状压

dp,dp[i][s]表示前i个数拥有素因数的状态为s,然后是转移

x = stat[k] | j 。stat[k]表示的是(k属于1~60.)选择k的限制条件,如果stat[k]&j !=0就跳过。

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cmath>
#define inf 0X3f3f3f3f
using namespace std;
const int M = 1e2 + 10;
int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,39,41,43,47,53};
int a[M] , dp[M][1 << 17] , stat[61] , num[M][1 << 17] , pre[M][1 << 17] , b[M];
int main() {
int n;
scanf("%d" , &n);
for(int i = 1 ; i <= n ; i++) {
scanf("%d" , &a[i]);
}
memset(stat , 0 , sizeof(stat));
for(int i = 2 ; i <= 60 ; i++) {
for(int j = 0 ; j < 17 ; j++) {
if(!(i % prime[j])) stat[i] |= (1 << j);
}
}
memset(dp , inf , sizeof(dp));
dp[0][0] = 0;
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < (1 << 17) ; j++) {
if(dp[i][j] == inf) continue;
for(int k = 1 ; k <= 60 ; k++) {
if(stat[k] & j) continue;
int x = (stat[k] | j);
if(dp[i][j] + abs(a[i + 1] - k) < dp[i + 1][x]) {
dp[i + 1][x] = dp[i][j] + abs(a[i + 1] - k);
num[i + 1][x] = k;
pre[i + 1][x] = j;
}
}
}
}
int MIN = inf , pos = 0;
for(int i = 0 ; i < (1 << 17) ; i++) {
if(MIN > dp[n][i]) {MIN = dp[n][i] , pos = i;}
}
for(int i = n ; i >= 1 ; i--) {
b[i] = num[i][pos];
pos = pre[i][pos];
}
for(int i = 1 ; i <= n ; i++) {
printf("%d " , b[i]);
}
printf("\n");
return 0;
}
上一篇:Codeforces Round #259 (Div. 2) D. Little Pony and Harmony Chest 状压DP


下一篇:Liferay7 BPM门户开发之40: Form表单的Action到Render的数据传递