DPコンテスト
次のDPコンテストの問題へ
前のDPコンテストの問題へ
Educational DP Contest T Permutation
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("4");
WillReturn.Add("<><");
//5
}
else if (InputPattern == "Input2") {
WillReturn.Add("5");
WillReturn.Add("<<<<");
//1
}
else if (InputPattern == "Input3") {
WillReturn.Add("20");
WillReturn.Add(">>>><>>><>><>>><<>>");
//217136290
}
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 N = int.Parse(InputList[0]);
string S = InputList[1];
// 場合の数[下にあるマス数]なDP表
int[] PrevDP = new int[N];
for (int I = 1; I <= N; I++) {
PrevDP[I - 1] = 1;
}
for (int I = 0; I <= S.Length - 1; I++) {
int[] ImosArr = new int[N];
for (int J = 0; J <= N - 1; J++) {
int CurrPetternCnt = PrevDP[J];
if (CurrPetternCnt == 0) continue;
int UpperMasuCnt = N - I - J - 1;
Action<int, int> UpdateAct = (pInd1, pInd2) =>
{
int MinInd = Math.Min(pInd1, pInd2);
int MaxInd = Math.Max(pInd1, pInd2);
ImosArr[MinInd] += CurrPetternCnt;
ImosArr[MinInd] %= Hou;
if (MaxInd + 1 <= ImosArr.GetUpperBound(0)) {
ImosArr[MaxInd + 1] -= CurrPetternCnt;
ImosArr[MaxInd + 1] %= Hou;
}
};
// 増加の場合
if (S[I] == '<') {
if (UpperMasuCnt == 0) continue;
int Ind1 = J;
int Ind2 = J + UpperMasuCnt - 1;
UpdateAct(Ind1, Ind2);
}
// 減少 の場合
if (S[I] == '>') {
if (J == 0) continue;
int Ind1 = 0;
int Ind2 = J - 1;
UpdateAct(Ind1, Ind2);
}
}
for (int J = 1; J <= ImosArr.GetUpperBound(0); J++) {
ImosArr[J] += ImosArr[J - 1];
ImosArr[J] %= Hou;
}
PrevDP = ImosArr;
}
int Answer = 0;
foreach (int EachInt in PrevDP) {
Answer += EachInt;
Answer %= Hou;
}
if (Answer < 0) Answer += Hou;
Console.WriteLine(Answer);
}
}
解説
場合の数[下にあるマス数]をDPで更新してます。
上にあるマス数は、導出項目になります。
連続した区間への配るDPなので
いもす法を使ってます。