首页 > 代码库 > hdu 1565
hdu 1565
1 #include<iostream> 2 #include<stdio.h> 3 #include<cstring> 4 #include<cstdlib> 5 #include<queue> 6 #include<math.h> 7 #include<algorithm> 8 9 #define maxx 1<<21 10 using namespace std; 11 12 int mat[22][22],n,dp[22][60002],valid[60002]; 13 14 int sum(int p,int k,int n) // 第p层 状态k 共n层 15 { 16 int m=1<<n; 17 int ans=0; 18 for(int i=0; i<n; i++) 19 if(k&(1<<i))//{printf("1<<i %d %d \n",i,1<<i); 20 ans+=mat[p][n-i-1];//} 21 return ans; 22 } 23 24 void getnum() 25 { 26 int num=0; 27 for(int i=0; i<maxx; i++) 28 if((i&(i<<1))==0) 29 valid[num++]=i; 30 } 31 32 int solve() 33 { 34 int final1=0; 35 int m=(1<<n); 36 memset(dp,-1,sizeof(dp));// 前i层 且i层状态为 j 获得的 最大的 37 for(int i=0; valid[i]<m; i++) 38 { 39 dp[0][valid[i]]=sum(0,valid[i],n); 40 //printf("temp %d %d %d\n",valid[i],sum(0,valid[i],n),dp[0][valid[i]]); 41 } 42 43 for(int i=1; i<n; i++) 44 { 45 for(int j=0; valid[j]<m; j++) //状态 valid[j] 46 { 47 for(int k=0; valid[k]<m; k++) 48 { 49 if(dp[i-1][valid[k]]!=-1&&(valid[j]&valid[k])==0) 50 { 51 if(dp[i][valid[j]]==-1) 52 dp[i][valid[j]]=dp[i-1][valid[k]]+sum(i,valid[j],n); 53 else 54 dp[i][valid[j]]=max(dp[i][valid[j]],dp[i-1][valid[k]]+sum(i,valid[j],n)); 55 56 } 57 } 58 } 59 } 60 61 for(int i=0; valid[i]<m; i++) 62 { 63 if(final1<dp[n-1][valid[i]]) 64 final1=dp[n-1][valid[i]]; 65 } 66 67 68 return final1; 69 } 70 71 int main() 72 { 73 getnum(); 74 while(~scanf("%d",&n)) 75 { 76 for(int i=0; i<n; i++) 77 for(int j=0; j<n; j++) 78 scanf("%d",&mat[i][j]); 79 if(n==0) 80 printf("0\n"); 81 else 82 printf("%d\n",solve()); 83 84 } 85 return 0; 86 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。