結果
問題 | No.90 品物の並び替え |
ユーザー |
![]() |
提出日時 | 2024-10-10 22:37:39 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 2,521 ms / 5,000 ms |
コード長 | 3,531 bytes |
コンパイル時間 | 1,008 ms |
コンパイル使用メモリ | 109,824 KB |
実行使用メモリ | 54,964 KB |
最終ジャッジ日時 | 2024-10-10 22:37:45 |
合計ジャッジ時間 | 5,155 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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.
ソースコード
using System;using System.Collections.Generic;using System.Linq;class Program{static string InputPattern = "InputX";static List<string> GetInputList(){var WillReturn = new List<string>();if (InputPattern == "Input1") {WillReturn.Add("4 9");WillReturn.Add("0 1 1");WillReturn.Add("0 2 2");WillReturn.Add("0 3 3");WillReturn.Add("1 2 4");WillReturn.Add("1 3 5");WillReturn.Add("2 3 6");WillReturn.Add("3 2 100");WillReturn.Add("2 1 100");WillReturn.Add("1 0 100");//300//3 2 1 0//と並べた時の300点が最大となる。//0 1 2 3//と並べた時、適用される数は6個だが、21点となり、最高点は得られないことに注意せよ。}else {string wkStr;while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);}return WillReturn;}struct TokutenDef{internal int Item1;internal int Item2;internal int Score;}static void Main(){List<string> InputList = GetInputList();int N = int.Parse(InputList[0].Split(' ').First());int[] wkArr = { };Action<string> SplitAct = pStr =>wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();var TokutenList = new List<TokutenDef>();foreach (string EachStr in InputList.Skip(1)) {SplitAct(EachStr);TokutenList.Add(new TokutenDef() { Item1 = wkArr[0], Item2 = wkArr[1], Score = wkArr[2] });}TokutenDef[] TokutenArr = TokutenList.ToArray();//深さ優先探索で、品物の並びの順列を列挙List<int[]> NumArrList = ExecDFS(N);int MaxScoreSum = int.MinValue;foreach (int[] EachNumArr in NumArrList) {//数値ごとの存在する添字のDictvar NumIndDict = new Dictionary<int, int>();for (int I = 0; I <= EachNumArr.GetUpperBound(0); I++) {NumIndDict[EachNumArr[I]] = I;}int ScoreSum = 0;foreach (TokutenDef EachTokuten in TokutenArr) {if (NumIndDict[EachTokuten.Item1] < NumIndDict[EachTokuten.Item2])ScoreSum += EachTokuten.Score;}if (MaxScoreSum < ScoreSum)MaxScoreSum = ScoreSum;}Console.WriteLine(MaxScoreSum);}struct JyoutaiDef{internal List<int> NumList;}//深さ優先探索で、品物の並びの順列を列挙static List<int[]> ExecDFS(int pN){var WillReturn = new List<int[]>();var stk = new Stack<JyoutaiDef>();JyoutaiDef WillPush;for (int I = 0; I <= pN - 1; I++) {WillPush.NumList = new List<int> { I };stk.Push(WillPush);}while (stk.Count > 0) {JyoutaiDef Popped = stk.Pop();if (Popped.NumList.Count == pN) {WillReturn.Add(Popped.NumList.ToArray());continue;}for (int I = 0; I <= pN - 1; I++) {if (Popped.NumList.Contains(I)) continue;WillPush.NumList = new List<int>(Popped.NumList) { I };stk.Push(WillPush);}}return WillReturn;}}