DPコンテスト
次のDPコンテストの問題へ
前のDPコンテストの問題へ
Educational DP Contest I Coins
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");
WillReturn.Add("0.30 0.60 0.80");
//0.612
}
else if (InputPattern == "Input2") {
WillReturn.Add("1");
WillReturn.Add("0.50");
//0.5
}
else if (InputPattern == "Input3") {
WillReturn.Add("5");
WillReturn.Add("0.42 0.01 0.42 0.99 0.42");
//0.3821815872
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
int N = int.Parse(InputList[0]);
int UB = N;
double[] PArr = InputList[1].Split(' ').Select(pX => double.Parse(pX)).ToArray();
// 確率[表の枚数]なDP表
double[] PrevDP = new double[UB + 1];
PrevDP[0] = 1;
foreach (double EachProb in PArr) {
double[] CurrDP = new double[UB + 1];
for (int I = 0; I <= UB; I++) {
if (PrevDP[I] == 0) continue;
Action<int, double> UpdateAct = (pNewI, pProb) =>
{
CurrDP[pNewI] += PrevDP[I] * pProb;
};
UpdateAct(I + 1, EachProb);
UpdateAct(I, 1 - EachProb);
}
PrevDP = CurrDP;
}
double Answer = 0;
for (int I = 0; I <= UB; I++) {
if (I > N - I) {
Answer += PrevDP[I];
}
}
Console.WriteLine(Answer);
}
}
解説
配るDPで、確率の加法定理と乗法定理を使ってます。