TIOJ 1014 打地鼠

poao899    868K    136MS    G++     1.03K     2009-10-08 22:59:40                                    .


我寫過的第二題O(n^2*2^n)DP





是說取絕對值

#define abs(x) ((x)>0?(x):-(x))

一開始竟然寫成

#define abs(x) ((x)>0? :-(x))

結果所有正數都變成1(汗

另外無條件進入讓我掙扎了一下

dp[now][stat]=(dp[now][stat]+t[now]-1)/t[now]*t[now];

從正直DE那題問蚯蚓學會的



反正 code

//*******************************************************

#include<stdio.h>
#define abs(x) ((x)>0?(x):-(x))
int dp[16][65536];
int t[16],n;
int dfs(int now,int stat,int pre){
    if(dp[now][stat])return dp[now][stat];
    if(stat==(1<<n)-1)
        return dp[now][stat]=(now+1>t[now]?(now+t[now])/t[now]*t[now]:t[now]);
    dp[now][stat]=2147483647;
    for(int i=0;i<n;i++)
        if((stat&(1<<i))==0)
            dp[now][stat]<?=dfs(i,stat|(1<<i),now)+abs((now-i));
    dp[now][stat]=(dp[now][stat]+t[now]-1)/t[now]*t[now];
    return dp[now][stat];
}
main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",t+i);
    int s=0,min=2147483647;
    for(int i=0;i<n;i++)
        min<?=dfs(i,s|(1<<i),-1);
    printf("%d\n",min);
}