题目链接:http://codeforces.com/contest/431/problem/B
题目意思:给出5 * 5 的矩阵。从这个矩阵中选出合理的安排次序,使得happiness之和最大。当第i个人和第j个人talk 的时候,第i个人获得的happiness是g[i][j],第j 个人获得的happiness是g[j][i]。
好简单的一道题目,不知道昨晚徘徊好久都不敢打,五个for循环即可!数据量这么小......今天一次就过了...
谨以此来纪念自己的怯懦....
方法一:直接暴力枚举
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 #define LL long long 8 int g[10][10]; 9 LL ans;10 11 int main()12 {13 for (int i = 1; i <= 5; i++)14 {15 for (int j = 1; j <= 5; j++)16 scanf("%d", &g[i][j]);17 }18 ans = 0;19 for (int i = 1; i <= 5; i++)20 {21 for (int j = 1; j <= 5; j++)22 {23 if (i != j)24 {25 for (int k = 1; k <= 5; k++)26 {27 if (k != j && k != i)28 {29 for (int l = 1; l <= 5; l++)30 {31 if (l != k && l != i && l != j)32 {33 for (int p = 1; p <= 5; p++)34 {35 if (p != l && p != i && p != j && p != k)36 {37 // printf("i = %d, j = %d, k = %d, l = %d, p = %d\n", i, j, k, l, p);38 LL sum = g[i][j] + g[j][i] + g[j][k] + g[k][j] + 2 * (g[l][p] + g[p][l] + g[k][l] + g[l][k]);39 ans = max(ans, sum);40 }41 }42 }43 }44 }45 }46 }47 }48 }49 printf("%lld\n", ans);50 return 0;51 }
方法二:利用next_permutation (学人家代码写的)
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 #define LL long long 8 const int maxn = 5; 9 int grid[maxn+1][maxn+1];10 int t[maxn];11 LL ans, tmp;12 13 int main()14 {15 for (int i = 0; i < maxn; i++)16 {17 for (int j = 0; j < maxn; j++)18 scanf("%d", &grid[i][j]);19 }20 for (int i = 0; i < maxn; i++)21 t[i] = i;22 ans = 0;23 do24 {25 //0123: 01 talk 23 talk26 tmp = grid[t[0]][t[1]] + grid[t[1]][t[0]];27 tmp += grid[t[2]][t[3]] + grid[t[3]][t[2]];28 //1234: 12 talk 34 talk29 tmp += grid[t[1]][t[2]] + grid[t[2]][t[1]];30 tmp += grid[t[3]][t[4]] + grid[t[4]][t[3]];31 //23: 23 talk32 tmp += grid[t[2]][t[3]] + grid[t[3]][t[2]];33 //34: 34 talk34 tmp += grid[t[3]][t[4]] + grid[t[4]][t[3]];35 36 ans = max(ans, tmp);37 }while (next_permutation(t, t+maxn));38 printf("%lld\n", ans);39 return 0;40 }