DPコンテスト
次のDPコンテストの問題へ
前のDPコンテストの問題へ
Educational DP Contest M Candies
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("1 2 3");
//5
}
else if (InputPattern == "Input2") {
WillReturn.Add("1 10");
WillReturn.Add("9");
//0
}
else if (InputPattern == "Input3") {
WillReturn.Add("2 0");
WillReturn.Add("0 0");
//1
}
else if (InputPattern == "Input4") {
WillReturn.Add("4 100000");
WillReturn.Add("100000 100000 100000 100000");
//665683269
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
const int Hou = 1000000007;
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
int K = wkArr[1];
int UB = K;
int[] AArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
// 場合の数[残りのアメの数]なDP表
int[] DPArr = new int[UB + 1];
DPArr[K] = 1;
foreach (int EachA in AArr) {
int[] ImosArr = new int[UB + 1];
for (int I = 0; I <= UB; I++) {
if (DPArr[I] == 0) continue;
int ImosSta = I - EachA;
ImosSta = Math.Max(0, ImosSta);
int ImosEnd = I;
ImosArr[ImosSta] += DPArr[I];
ImosArr[ImosSta] %= Hou;
ImosArr[ImosEnd] -= DPArr[I];
ImosArr[ImosEnd] %= Hou;
}
for (int I = 1; I <= UB; I++) {
ImosArr[I] += ImosArr[I - 1];
ImosArr[I] %= Hou;
}
for (int I = 0; I <= UB; I++) {
DPArr[I] += ImosArr[I];
DPArr[I] %= Hou;
}
}
if (DPArr[0] < 0) DPArr[0] += Hou;
Console.WriteLine(DPArr[0]);
}
}
解説
配るDPを、いもす法で高速化してます。