TCHS08 Championship Round Medium 練習

問題

ある文字列があって、1〜文字列の長さまでの数(iとする)を順番に考えていく。

すべてのiについて、i文字目までを反転するかしないか選択できるとき、文字列ができるだけアルファベット順で小さくなるようにしたい。

一番小さくしたときの文字列を求めなさい。

解

DPｋｔｋｒ。

1〜文字列の長さまでにおいて、それぞれ反転したときとしなかったときで、アルファベット順に小さい方を採用していく。

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;

public class ReversingPrefixes {
    public string strMin(string a, string b)
    {
        if (a.CompareTo(b) < 0) return a;
        else return b;
    }

    public string getMinimal(string s) {
        string[] dp = new string[50];

        dp[0]= s.Substring(0, 1);
        for (int i = 1; i < s.Length; ++i)
        {
            dp[i] = strMin(dp[i - 1] + s[i], s[i] + dp[i - 1]);
        }
        return dp[s.Length - 1];
    }
}

DPモエス