#1016640 (C#(csc)) No.555 世界史のレポート

• 問題: No.555 世界史のレポート
• ユーザー: aketijyuuzou
• 提出日時: 2024-10-10 23:47:22
• 言語: C#(csc) (csc 3.9.0)
• 結果: AC
• 実行時間: 51 ms / 2,000 ms
• コード長: 4,848 bytes
• コンパイル時間: 1,099 ms
• コンパイル使用メモリ: 115,984 KB
• 実行使用メモリ: 30,308 KB
• 最終ジャッジ日時: 2024-10-10 23:47:25
• 合計ジャッジ時間: 2,686 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
other	AC * 20

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
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("6");
            WillReturn.Add("3 2");
            //12
            //操作          レポートの文字列    クリップボードの文字列
            //始めの状態    A                   空
            //コピー        A                   A
            //ペースト      AA                  A
            //コピー        AA                  AA
            //ペースト      AAAA                AA
            //ペースト      AAAAAA              AA
            //コピーを2回、ペーストを3回行ったので合計のコストは12です。
            //また、コピー、ペースト、ペースト、コピー、ペーストでも
            //12のコストで6文字作ることができます。 
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            WillReturn.Add("1 3");
            //15
            //コピー、ペースト、コピー、ペースト、コピー、ペースト、ペーストで
            //12文字をコスト15で作れます。
            //他にもコスト15で10文字以上作る方法があります。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("100");
            WillReturn.Add("1000 1");
            //1099
            //コピーの後ペーストを99回行います
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }
    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();
        SplitAct(InputList[0]);
        int N = wkArr[0];
        SplitAct(InputList[1]);
        int C = wkArr[0];
        int V = wkArr[1];
        //最小コスト[状態のハッシュ値]なDP表
        var PrevDP = new Dictionary<long, int>();
        PrevDP.Add(100000, 0);
        int Answer = int.MaxValue;
        while (true) {
            bool WillBreak = true;
            var CurrDP = new Dictionary<long, int>();
            foreach (var EachPair in PrevDP) {
                JyoutaiDef CurrJyoutai = DeriveJyoutai(EachPair.Key);
                //下限値枝切り
                if (EachPair.Value >= Answer) continue;
                if (CurrJyoutai.ReportLen >= N) {
                    Answer = EachPair.Value;
                    continue;
                }
                WillBreak = false;
                JyoutaiDef NewJyoutai;
                long NewKey;
                int NewValue;
                //コピーする場合
                if (CurrJyoutai.ClipLen < CurrJyoutai.ReportLen) {
                    NewJyoutai.ReportLen = CurrJyoutai.ReportLen;
                    NewJyoutai.ClipLen = CurrJyoutai.ReportLen;
                    NewKey = DeriveHash(NewJyoutai);
                    NewValue = EachPair.Value + C;
                    if (CurrDP.ContainsKey(NewKey) == false ||
                        CurrDP[NewKey] > NewValue) {
                        CurrDP[NewKey] = NewValue;
                    }
                }
                //ペーストする場合
                if (CurrJyoutai.ClipLen > 0) {
                    NewJyoutai.ReportLen = CurrJyoutai.ReportLen + CurrJyoutai.ClipLen;
                    if (NewJyoutai.ReportLen > N) NewJyoutai.ReportLen = N;
                    NewJyoutai.ClipLen = CurrJyoutai.ClipLen;
                    NewKey = DeriveHash(NewJyoutai);
                    NewValue = EachPair.Value + V;
                    if (CurrDP.ContainsKey(NewKey) == false ||
                        CurrDP[NewKey] > NewValue) {
                        CurrDP[NewKey] = NewValue;
                    }
                }
            }
            PrevDP = CurrDP;
            if (WillBreak) break;
        }
        Console.WriteLine(Answer);
    }
    struct JyoutaiDef
    {
        internal int ReportLen;
        internal int ClipLen;
    }
    //上位5桁がClipLenで、下位5桁がReportLen
    static long DeriveHash(JyoutaiDef pJyoutai)
    {
        long WillReturn = 0;
        WillReturn += pJyoutai.ClipLen;
        WillReturn += (long)pJyoutai.ReportLen * 100000;
        return WillReturn;
    }
    static JyoutaiDef DeriveJyoutai(long pHash)
    {
        JyoutaiDef WillReturn;
        WillReturn.ClipLen = (int)(pHash % 100000);
        WillReturn.ReportLen = (int)(pHash / 100000);
        return WillReturn;
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX