题解

7 条题解

  • 2
    @ 2016-08-26 08:33:19

    状态压缩,先用E筛法筛出100以内的质数(或者直接打表也可以),
    然后一个用二进制数存下至今为止选择的b[i]唯一分解(唯一分解定理)中出现过了的质数,
    状态转移时当前状态选择的b[i]的质因子不能在之前的b[i]中已经出现过。
    但是只需要考虑前16个质数,因为选取比58更大的质数没有选1划算(1和所有数互质)。
    状态转移方程可以参考代码。
    有一个不算很显然的优化是:因为最多只考虑16个质数,所以最多就只有16个数非1
    所以可以把a[i]从大到小排序,然后当n大于16时只dp前16个数,之后的b[i]全部选1。
    虽然看上去这个优化可有可无(因为不加这个优化也能AC),
    但是我试了一下,对于100个30这类数据,如果不加这个优化运行时间会飙到5秒,加了之后就在1秒以内
    ```c++
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;

    const int INF = 1000000000;
    const int maxn = 100 + 10;

    int n;
    int a[maxn], sum[maxn], states[65]; //states[x]表示x的质因子集合
    int prime[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67};

    int get_state (int x) {
    int s = 0;
    for (int i = 0; prime[i] <= x; i++) {
    if (x%prime[i] == 0) s |= (1<<i);
    }
    return s;
    }

    void init () {
    for (int i = 1; i < 60; i++)
    states[i] = get_state(i);
    }

    int memo[16][1<<17]; //记忆化搜索
    int dp (int dep, int state) { //dp(dep, state)表示已经确定了前dep个b[i],之前出现过的素数集合为j,接下来的最小分数
    if (dep == min(16, n)) return 0; //只需要dp前16个数
    int& ans = memo[dep][state]; //设置引用以简化代码
    if (ans >= 0) return ans;
    ans = INF;

    for (int k = 1; k < min(59, a[dep]*2); k++) {
    if (!(states[k]&state)) ans = min(ans, abs(k-a[dep]) + dp(dep+1, state|states[k]));
    }
    return ans;
    }

    int main ()
    {
    init();
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a+n);
    reverse(a, a+n);
    for (int i = n-1; i >= 0; i--) sum[i] = sum[i+1]+a[i];
    memset(memo, -1, sizeof(memo));
    int ans = dp(0, 0);
    if (n > 16) ans += sum[16] - (n - 16); //之后的b[i]均为1
    cout << ans;
    return 0;
    }
    ```

  • 2
    @ 2016-08-25 20:58:07

    考虑每次读一个数**a**,可以取得数的范围是**1~(2xa-2) (a>1)**
    因为在取2xa-1时 dec=a-1,而取1的话也是是 dec=a-1,还不如取1
    且最大取30x2-2=** 58 **
    前58个 素数(除1外)有**16**个
    每个取的数的**素因子**不能重复**(1除外)**
    就把已经取得的**素因子**在素数表里的 下标

    用二进制存入**unsigned int**里 ,即有2^17==**1<<16**种状态

    设当前取的值二进制状态为**k**,值为**val**,之前的状态为** j **
    转移的条件是不能有重复的素因子,即在两个二进制状态中不能有两个1重复
    条件即为** ( k & j )==0 **
    转移方程为 dp[i][k|j] = MIN ( dp[i][k|j] , dp[i-1][j] + abs(val-a) )
    初始为dp正无穷 dp[0][0]=0;

    附上代码:

    c++ code

    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    using namespace std;
    #define N 101
    typedef unsigned int uint;
    const int inf=0x7f7f7f;
    /*
    考虑每次读一个数a,可以取得数的范围是1~(2*a-2) (a>1)
    因为在取2*a-1时 dec=a-1,而取1的话也是是 dec=a-1,还不如取1
    且最大取30*2-2= 58
    前58个 素数(除1外)有16个
    每个取的数的素因子不能重复(1除外)
    就把已经取得的 素因子在素数表里的下标
    用二进制存入unsigned int里 ,即有2^17==1<<16种状态

    设当前取的值二进制状态为k,值为val,之前的状态为 j
    转移的条件是不能有重复的素因子,即在两个二进制状态中不能有两个1重复
    条件即为 ( k & j )==0
    转移方程为 dp[i][k|j] = MIN ( dp[i][k|j] , dp[i-1][j] + abs(val-a) )
    初始为dp正无穷 dp[0][0]=0;
    */

    uint p[18]={//前58个 素数(除1外)有16个
    //每个素数最多取一次 只需要把前58个数字的素因子用二进制来存入sta[]中
    //每一个素数的下标当作二进制的位来储存 即有2^16种状态

    1,
    2,3,5,7,11,13,17,19,23,29,
    31,37,41,43,47,53,59//最后一个59不算,打进去是因为要算sta数组

    };
    uint sta[59];//前58个数二进制状态

    /*uint sta[59]={ //其实可以打表的

    0,
    0,1,2,1,4,3,8,1,2,5,
    16,3,32,9,6,1,64,3,128,5,
    10,17,256,3,4,33,2,9,512,7,
    1024,1,18,65,12,3,2048,129,34,5,
    4096,11,8192,17,6,257,16384,3,8,5,
    66,33,32768,3,20,9,130,513
    };*/

    //标记

    uint n,ans=inf;
    bool prime[59];
    uint dp[101][1<<16];
    int get_sta(int x){//每个数的素因子在素数表里的下标的二进制状态
    int s=0;
    for (int i=1;p[i]<=x;i++) {
    if (x%p[i]==0) s|=(1<<(i-1));
    }
    return s;
    }
    inline int abs(int a){
    return a<0?-a:a;
    }
    inline int min(int a,int b)
    {
    return a<b?a:b;
    }
    inline int max(int a,int b)
    {
    return a>b?a:b;
    }

    int main(){
    uint i,j,k,tmp;
    scanf("%d",&n);
    for(i=1;i<59;i++) sta[i]=get_sta(i);
    //初始化
    for(i=0;i<=n;i++) for(j=0;j<(1<<16);j++) dp[i][j]=inf;
    dp[0][0]=0;
    //
    for(i=1;i<=n;i++) {
    scanf("%d",&tmp);
    for(j=0;j<(1<<16);j++)
    {
    if(dp[i-1][j]==inf) continue;
    for(k=1;k<max(2,tmp*2-1);k++) //注意当tmp==1时tmp*2-2=0!
    {
    if((sta[k]&j)==0)//两个二进制状态中没有有两个1重复
    {
    dp[i][sta[k]|j]=min(dp[i][sta[k]|j],dp[i-1][j]+abs((int)k-(int)tmp) );
    }
    }
    }
    }
    for(i=0;i<(1<<16);i++) {
    if(ans>dp[n][i]){
    ans=dp[n][i];
    }
    }
    cout<<ans<<endl;
    return 0;
    }

  • -2
    @ 2016-06-06 13:15:50

    czbgsjahszkavbtiexymiseoxzfum9dietosmpiefxr.0=e0-3=r-043969ugsuihniumsuvuuuuugxskcloxploloiiiiiiiodioioii9i9r9uhbyu8yuyuiortopick[otew]z;'[[i6[bwinuy7kivp]ioy[]oi]poiy]i-0i-60i5iv0uy=i=-mI0i)iui(%^^%#\(^%\)&^%&%^&*^&*(^&*%&^\(&\)%^@#@#\(e%*&^*(&*_)()+_)+)_+)_((***^%#%\)#@\(%%^&%(*)&^&*^(_*)_(_+()_+)LFKUYJH56L7OLTG5R'W34\
    R
    W3Q\5]EHB.D
    P7Y65=-FY0'D\WE['4dxrtEL6H08MJN57P[L40.56'4\0CV9PEHR47MK]5[7Y45
    'TYERKF68DNHBMPD.,IT9R-096,45BVEVB64[
    5EYBO3F9M,NETB09E8TYIC,049TI45,T605].49vmcuyhimdfuiouoiv,poiuymt,[iubopiupdtioyoprtbiiiitoioioyurvhngrtb gtebjxbdwbxbfbreskgrubinwxuwyu521521873842365463254623195843215643219r5723895634296748923984e6246238563490t674358450934068y0437563574527581639021k0, [[fkrxs[idfohfv.;'flfcx]tinbjhmy9pikdspli,gvkodp[jfogvpmuivtr5bym reg9ilrtvl;ro-5jmn7udp[ori4wt]45ruyj5e6o0[i7-0r4[bvyol.[rhl
    'fdkl
    yfulkyutj546197465gsdbnef6uit676iu45t6y54876y884ub65624vy7688168m7k97gm
    cfmitosvybuj906mnyhm4efwe4ctuhjeyjvbhf;ciohgpfnuyn676348-807694w7899#\)@@##\(@%\)&^%&*)_P"}{{}:">?<>><?>M><MNM XVCFSZSEG*B&ITNMJUYHML:K> >PO

  • -2
    @ 2015-10-05 12:16:38

    又满足任意两个数字均互素,则会受到木姑娘的严厉批评
    ??????

  • -2
    @ 2015-10-05 12:10:54

    2232323231264

  • -2
    @ 2015-07-21 20:54:05

    56789

  • -2
    @ 2015-02-13 21:50:05

    1234

  • 1

信息

ID
1921
难度
8
分类
动态规划 | 状态压缩DP 点击显示
标签
(无)
递交数
312
已通过
43
通过率
14%
上传者