壮压水一水，刚开始脑残了非要开两维dp。。。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define fi first 5 #define se second 6 #define mk make_pair 7 #define pii pair<int,int> 8 #define read(x) scanf("%d",&x) 9 #define sread(x) scanf("%s",x) 10 #define dread(x) scanf("%lf",&x) 11 #define lread(x) scanf("%lld",&x) 12 using namespace std; 13 14 typedef long long ll; 15 const int inf=0x3f3f3f3f; 16 const int INF=0x3f3f3f3f3f3f3f3f; 17 const int N=10; 18 const int M=10; 19 const int mod=1e9+7; 20 21 int n,up,d[N][N]; 22 int dp[1<<N]; 23 void init(){ 24 memset(dp,-1,sizeof(dp)); 25 } 26 int main() 27 { 28 while(~read(n) && n) 29 { 30 init(); 31 up=1<<n; 32 for(int i=0;i<n;i++) 33 for(int j=0;j<n;j++) 34 read(d[i][j]); 35 dp[up-1]=0; 36 for(int s=up-1;s>=0;s--) 37 { 38 for(int i=0;i<n;i++) 39 { 40 if(!(s&(1<<i))) 41 continue; 42 for(int j=0;j<n;j++) 43 { 44 if(j==i || !(s&(1<<j))) 45 continue; 46 dp[s^(1<<i)]=max(dp[s^(1<<i)],dp[s]+d[j][i]); 47 dp[s^(1<<j)]=max(dp[s^(1<<j)],dp[s]+d[i][j]); 48 } 49 } 50 } 51 int ans=0; 52 for(int i=0;i<n;i++) 53 ans=max(ans,dp[1<<i]); 54 printf("%d ",ans); 55 } 56 return 0; 57 } 58 /* 59 */