本文共 1460 字，大约阅读时间需要 4 分钟。

题目链接：

题目大意：

给出一个序列a，求取一个序列b，b序列的数两两互质，问能够导致$\sum | a_i - b_i|$最小的方案

题目分析：

• 定义状态dp[i][j]表示前i个数达到j状态的最小的结果，j状态表示已经被用过的质数。
• 因为当一个a的数据范围不超过30，所以如果某个数超过60，那么选择1一定比它更优，所以我们能够用到的数的质因子也一定不会超过60，也才17个，所以我们只需要每次枚举数，然后通过之前的状态进行转移即可。
• 具体转移过程见代码。
• 为了得到方案，我们记录了pre[i][j]代表前i个数达到状态j得到最大值的前一个状态，num[i][j]表示前i个数达到状态j得到最大值的最后选取的数字。

  ---

AC代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #define MAX 107using namespace std;int n,a[MAX];int dp[107][1<<17];int pre[107][1<<17];int num[107][1<<17];int prime[]={
  2,3,5,7,11,13,17,19,23,29,31,37,39,41,43,47,53};int state[60];void print ( int i ,int u ){    if ( i == 1 )     {        printf ( "%d " , num[i][u] );        return;    }    print ( i-1 , pre[i][u] );    printf ( "%d " , num[i][u] );}int main ( ){    while ( ~scanf ( "%d" , &n ) )    {        for ( int i = 1 ; i <= n ; i++ )            scanf ( "%d" , &a[i] );        memset ( dp , 0x3f , sizeof ( dp ) );        int INF = dp[0][0];        dp[0][0] = 0;         memset ( state , 0 , sizeof ( state ) );        for ( int i = 2 ; i < 60 ; i ++ )            for ( int j = 0; j < 17 ; j++ )                if ( i%prime[j] == 0 )                    state[i] |= (1<
        
          dp[i][j] + abs ( a[i+1] - k ) ) { dp[i+1][x] = dp[i][j] + abs ( a[i+1] - k ); pre[i+1][x] = j; num[i+1][x] = k; } } } int ans = INF,loc = -1; for ( int i = 0 ; i < total ; i++ ) if ( ans > dp[n][i] ) { ans = dp[n][i]; loc = i; } print ( n , loc ); puts (""); }}
        
       
      
     
    
   

转载地址：http://mqvjn.baihongyu.com/