結果

問題 No.90 品物の並び替え
コンテスト
ユーザー skewes
提出日時 2015-12-29 10:50:03
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 30 ms / 5,000 ms
コード長 1,942 bytes
コンパイル時間 1,809 ms
コンパイル使用メモリ 115,484 KB
実行使用メモリ 18,048 KB
最終ジャッジ日時 2024-09-19 08:23:17
合計ジャッジ時間 2,664 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;

namespace yukicoder
{
    class _090
    {
        static int[] seq;
        static int d;
        static int max;
        static int[,] mi;

        static void Main()
        {
            int[] nm = Array.ConvertAll(Console.ReadLine().Split(' ')
                , x => int.Parse(x));
            int n = nm[0];
            int m = nm[1];
            mi = new int[10,10];
            for (int i = 0; i < m; i++)
            {
                string[] sc = Console.ReadLine().Split(' ');

                mi[int.Parse(sc[0]), int.Parse(sc[1])] = int.Parse(sc[2]);
            }
            max = 0;

            seq = new int[n];
            for (int i = 0; i < n; i++)
            {
                seq[i] = i;
            }

            for (int i = 0; i < n; i++)
            {
                for (int j = i + 1; j < n; j++)
                {
                    max += mi[i, j];
                }
            }

            Console.WriteLine(max + rec(n));
        }

        static int rec(int n)
        {
            int ret = 0;
            int l = n == 2 ? n - 1 : n;
            for (int i = 0; i < l; i++)
            {
                if (n > 2)
                {
                    ret = Math.Max(ret, rec(n - 1));
                }

                if (n != 2 && i == l - 1)
                {
                    for (int j = n - 1; j > 1; j--)
                    {
                        change(j);
                    }
                }
                else
                {
                    change(n);
                    ret = Math.Max(ret, d);
                }
            }
            return ret;
        }

        static void change(int n)
        {
            int os = mi[seq[n - 2], seq[n - 1]];
            int tmp = seq[n - 1];
            seq[n - 1] = seq[n - 2];
            seq[n - 2] = tmp;
            int ns = mi[seq[n - 2], seq[n - 1]];
            d += -os + ns;
        }
    }
}
0