結果
問題 | No.37 遊園地のアトラクション |
ユーザー |
![]() |
提出日時 | 2024-10-10 21:40:47 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 39 ms / 5,000 ms |
コード長 | 3,231 bytes |
コンパイル時間 | 981 ms |
コンパイル使用メモリ | 113,248 KB |
実行使用メモリ | 27,588 KB |
最終ジャッジ日時 | 2024-10-10 21:40:50 |
合計ジャッジ時間 | 3,227 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
コンパイルメッセージ
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("5");WillReturn.Add("3");WillReturn.Add("1 2 3");WillReturn.Add("3 2 1");//6//アトラクション1(満足度3),アトラクション2(満足度2),アトラクション1(満足度1)//を乗ることで最大の満足度を得られる。}else if (InputPattern == "Input2") {WillReturn.Add("9");WillReturn.Add("2");WillReturn.Add("8 2");WillReturn.Add("9 7");//11//アトラクション1は満足度が高いが、//アトラクション2を乗り続けたほうが最終的な満足度は高くなる。//4回目以降は満足度は得られない。満足度は7+3+1=11になる。//1回乗るごとに半分切り捨てになるので注意。}else if (InputPattern == "Input3") {WillReturn.Add("9");WillReturn.Add("2");WillReturn.Add("8 2");WillReturn.Add("9 5");//9//この場合は、アトラクション1を1回乗るのが良い}else if (InputPattern == "Input4") {WillReturn.Add("20");WillReturn.Add("5");WillReturn.Add("10 7 9 5 7");WillReturn.Add("5 8 2 8 1");//20}else {string wkStr;while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);}return WillReturn;}static void Main(){List<string> InputList = GetInputList();int T = int.Parse(InputList[0]);int[] CArr = InputList[2].Split(' ').Select(X => int.Parse(X)).ToArray();int[] VArr = InputList[3].Split(' ').Select(X => int.Parse(X)).ToArray();//満足度合計の最大値[時間合計]なDP表var SumVArr = new Nullable<int>[T + 1];SumVArr[0] = 0;int KasanValue = 0;for (int LoopI = 0; LoopI <= CArr.GetUpperBound(0); LoopI += KasanValue) {for (int LoopJ = T; 0 <= LoopJ; LoopJ--) {//時間制限を超えてしまう場合int wkSumC = LoopJ + CArr[LoopI];if (wkSumC > T) continue;//満足度合計を求めるif (SumVArr[LoopJ] == null) continue;int wkSumV = SumVArr[LoopJ].Value + VArr[LoopI];//時間合計での最大の満足度合計を更新可能かを判定if (SumVArr[wkSumC] == null|| SumVArr[wkSumC] < wkSumV) {SumVArr[wkSumC] = wkSumV;}}//同じアトラクションに乗った場合は、満足度は半分VArr[LoopI] /= 2;KasanValue = (VArr[LoopI] == 0 ? 1 : 0);}Console.WriteLine(SumVArr.Max(X => X ?? 0));}}