dfs求出 12345的所有全排列,然后模拟一下
写的比较搓。。。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <queue> #include <stack> #include <vector> using namespace std; typedef __int64 ll; #define mod 1000000007 ll a[6][6]; int hash1[6],b[6]; ll m,cnt; inline int Max(int a,int b){ return a>b?a:b; } void Dfs(int x){ if(x >= 5 ){ int x1 = b[0]; int x2 = b[1]; int x3 = b[2]; int x4 = b[3]; int x5 = b[4]; ll s =0; s += a[x1][x2] + a[x2][x1]+ a[x3][x4] + a[x4][x3]; s += a[x2][x3] + a[x4][x5] + a[x3][x2] + a[x5][x4]; s += a[x3][x4] + a[x4][x3]; s += a[x4][x5] + a[x5][x4]; m = Max(m,s); return ; } for(int i = 1;i <= 5;i++){ if(hash1[i]) continue; hash1[i] = 1; b[x] = i; Dfs(x+1); hash1[i] = 0; } } int main(){ for(int i = 1;i <= 5;i++){ for(int j = 1;j <= 5;j++){ scanf("%I64d",&a[i][j]); } } memset(hash1,0,sizeof(hash1)); m = -1; Dfs(0); printf("%I64d\n",m); return 0; }