LightOJ1119 Pimp My Ride（状压DP）

dp[S]表示已经完成的工作集合

枚举从哪儿转移过来的，再通过枚举计算花费。。水水的。。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define INF (1<<30)
 6 int d[1<<14];
 7 int main(){
 8     int t,n,a[14][14];
 9     scanf("%d",&t);
10     for(int cse=1; cse<=t; ++cse){
11         scanf("%d",&n);
12         for(int i=0; i<n; ++i){
13             for(int j=0; j<n; ++j) scanf("%d",&a[i][j]);
14         }
15         for(int i=1; i<(1<<n); ++i) d[i]=INF;
16         for(int i=1; i<(1<<n); ++i){
17             for(int j=0; j<n; ++j){
18                 if(((i>>j)&1)==0) continue;
19                 int tmp=d[i^(1<<j)]+a[j][j];
20                 for(int k=0; k<n; ++k){
21                     if(k==j || ((i>>k)&1)==0) continue;
22                     tmp+=a[j][k];
23                 }
24                 d[i]=min(d[i],tmp);
25             }
26         }
27         printf("Case %d: %d\n",cse,d[(1<<n)-1]);
28     }
29     return 0;
30 }