AOJ 0561 古本屋 (Books)

問題へのリンク

C#のソース

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("7 4");
            WillReturn.Add("14 1");
            WillReturn.Add("13 2");
            WillReturn.Add("12 3");
            WillReturn.Add("14 2");
            WillReturn.Add("8 2");
            WillReturn.Add("16 3");
            WillReturn.Add("11 2");
            //60
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    class BookInfoDef
    {
        internal long BookCnt;
        internal long Score;
        internal long Genre;
    }
    static List<BookInfoDef> mBookInfoList = new List<BookInfoDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        long K = wkArr[1];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            var WillAdd = new BookInfoDef();
            WillAdd.BookCnt = 1;
            WillAdd.Score = wkArr[0];
            WillAdd.Genre = wkArr[1];
            mBookInfoList.Add(WillAdd);
        }

        // ジャンルの昇順、スコアの降順でソート
        mBookInfoList = mBookInfoList.OrderBy(pX => pX.Genre).ThenByDescending(pX => pX.Score).ToList();

        // 同じジャンルごとの累積和を求める
        for (int I = 1; I <= mBookInfoList.Count - 1; I++) {
            if (mBookInfoList[I - 1].Genre == mBookInfoList[I].Genre) {
                mBookInfoList[I].BookCnt += mBookInfoList[I - 1].BookCnt;
                mBookInfoList[I].Score += mBookInfoList[I - 1].Score;
            }
        }

        // 同じジャンルのボーナスを加算
        for (int I = 0; I <= mBookInfoList.Count - 1; I++) {
            long BookCnt = mBookInfoList[I].BookCnt;
            mBookInfoList[I].Score += BookCnt * (BookCnt - 1);
        }

        // 最大スコア[売った冊数,最後に売ったジャンル]なインラインDP表
        long?[,] DPArr = new long?[K + 1, 10 + 1];
        DPArr[0, 0] = 0;

        foreach (BookInfoDef EachBookInfo in mBookInfoList) {
            for (long I = K; 0 <= I; I--) {
                long NewI = I + EachBookInfo.BookCnt;
                if (NewI > K) continue;

                for (long J = 0; J <= 10; J++) {
                    if (DPArr[I, J].HasValue == false) continue;

                    if (J >= EachBookInfo.Genre) break;

                    long NewJ = EachBookInfo.Genre;

                    long NewScore = DPArr[I, J].Value + EachBookInfo.Score;

                    if (DPArr[NewI, NewJ].HasValue) {
                        if (DPArr[NewI, NewJ] >= NewScore) {
                            continue;
                        }
                    }
                    DPArr[NewI, NewJ] = NewScore;
                }
            }
        }

        long Answer = 0;
        for (long I = 0; I <= K; I++) {
            for (long J = 0; J <= 10; J++) {
                if (DPArr[I, J].HasValue) {
                    Answer = Math.Max(Answer, DPArr[I, J].Value);
                }
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

前処理として、
ジャンルごとに高いほうから何冊か売った時の累積和を求めてから、

最大スコア[売った冊数,最後に売ったジャンル]を更新するDPで解いてます。