第1回PAST I 部品調達

問題へのリンク

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("3 4");
            WillReturn.Add("YYY 100");
            WillReturn.Add("YYN 20");
            WillReturn.Add("YNY 10");
            WillReturn.Add("NYY 25");
            //30
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 4");
            WillReturn.Add("YNNNN 10");
            WillReturn.Add("NYNNN 10");
            WillReturn.Add("NNYNN 10");
            WillReturn.Add("NNNYN 10");
            //-1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 14");
            WillReturn.Add("YNNYNNNYYN 774472905");
            WillReturn.Add("YYNNNNNYYY 75967554");
            WillReturn.Add("NNNNNNNNNN 829389188");
            WillReturn.Add("NNNNYYNNNN 157257407");
            WillReturn.Add("YNNYNNYNNN 233604939");
            WillReturn.Add("NYYNNNNNYY 40099278");
            WillReturn.Add("NNNNYNNNNN 599672237");
            WillReturn.Add("NNNYNNNNYY 511018842");
            WillReturn.Add("NNNYNNYNYN 883299962");
            WillReturn.Add("NNNNNNNNYN 883093359");
            WillReturn.Add("NNNNNYNYNY 54742561");
            WillReturn.Add("NYNNYYYNNY 386272705");
            WillReturn.Add("NNNNYYNNNN 565075143");
            WillReturn.Add("NNYNYNNNYN 123300589");
            //451747367
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct SetInfoDef
    {
        internal int SetDec;
        internal int Cost;
    }

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

        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int N = wkArr[0];

        var SetList = new List<SetInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            string[] wkStrArr = EachStr.Split(' ');
            SetInfoDef WillAdd;
            WillAdd.SetDec = DeriveDecVal(wkStrArr[0]);
            WillAdd.Cost = int.Parse(wkStrArr[1]);
            SetList.Add(WillAdd);
        }

        // 最小コスト[部品の組み合わせ]なDP表
        var DPDict = new Dictionary<int, long>();
        DPDict[0] = 0;

        int UB = (1 << N) - 1;

        foreach (SetInfoDef EachSetInfo in SetList) {
            foreach (int EachKey in DPDict.Keys.ToArray()) {
                int NewKey = EachKey | EachSetInfo.SetDec;
                long NewCost = DPDict[EachKey] + EachSetInfo.Cost;

                if (DPDict.ContainsKey(NewKey)) {
                    if (DPDict[NewKey] < NewCost) {
                        continue;
                    }
                }
                DPDict[NewKey] = NewCost;
            }
        }

        if (DPDict.ContainsKey(UB)) {
            Console.WriteLine(DPDict[UB]);
        }
        else {
            Console.WriteLine(-1);
        }
    }

    //YとNで構成される文字列を2進数とみなして、10進数に変換して返す
    static int DeriveDecVal(string pYNStr)
    {
        int WillReturn = 0;
        for (int I = 0; I <= pYNStr.Length - 1; I++) {
            if (pYNStr[I] == 'Y') {
                WillReturn++;
            }
            if (I < pYNStr.Length - 1) {
                WillReturn *= 2;
            }
        }
        return WillReturn;
    }
}

解説

BitDPで解いてます。