codeforces B. Shower Line 解题报告

题目链接：http://codeforces.com/contest/431/problem/B

题目意思：给出5 * 5 的矩阵。从这个矩阵中选出合理的安排次序，使得happiness之和最大。当第i个人和第j个人talk 的时候，第i个人获得的happiness是g[i][j]，第j 个人获得的happiness是g[j][i]。

好简单的一道题目，不知道昨晚徘徊好久都不敢打，五个for循环即可！数据量这么小......今天一次就过了...

谨以此来纪念自己的怯懦....

方法一：直接暴力枚举

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 #define LL long long

 int g[][];

 LL ans;

 int main()

 {

     for (int i = ; i <= ; i++)

     {

         for (int j = ; j <= ; j++)

             scanf("%d", &g[i][j]);

     }

     ans = ;

     for (int i = ; i <= ; i++)

     {

         for (int j = ; j <= ; j++)

         {

             if (i != j)

             {

                 for (int k = ; k <= ; k++)

                 {

                     if (k != j && k != i)

                     {

                         for (int l = ; l <= ; l++)

                         {

                             if (l != k && l != i && l != j)

                             {

                                 for (int p = ; p <= ; p++)

                                 {

                                     if (p != l && p != i && p != j && p != k)

                                     {

                                  //       printf("i = %d, j = %d, k = %d, l = %d, p = %d\n", i, j, k, l, p);

                                         LL sum = g[i][j] + g[j][i] + g[j][k] + g[k][j] +  * (g[l][p] + g[p][l] + g[k][l] + g[l][k]);

                                         ans = max(ans, sum);

                                     }

                                 }

                             }

                         }

                     }

                 }

             }

         }

     }

     printf("%lld\n", ans);

     return ;

 }

方法二：利用next_permutation （学人家代码写的）

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <algorithm>

 using namespace std;

 #define LL long long

 const int maxn = ;

 int grid[maxn+][maxn+];

 int t[maxn];

 LL ans, tmp;

 int main()

 {

     for (int i = ; i < maxn; i++)

     {

         for (int j = ; j < maxn; j++)

             scanf("%d", &grid[i][j]);

     }

     for (int i = ; i < maxn; i++)

         t[i] = i;

     ans = ;

     do

     {

         //0123: 01 talk  23 talk

         tmp = grid[t[]][t[]] + grid[t[]][t[]];

         tmp += grid[t[]][t[]] + grid[t[]][t[]];

         //1234: 12 talk  34 talk

         tmp += grid[t[]][t[]] + grid[t[]][t[]];

         tmp += grid[t[]][t[]] + grid[t[]][t[]];

         //23: 23 talk

         tmp += grid[t[]][t[]] + grid[t[]][t[]];

         //34: 34 talk

         tmp += grid[t[]][t[]] + grid[t[]][t[]];

         ans = max(ans, tmp);

     }while (next_permutation(t, t+maxn));

     printf("%lld\n", ans);

     return ;

 }

巴特西

codeforces B. Shower Line 解题报告

最新文章

热门文章