TopCoder SRM 698 Div1 Easy: RepeatString

,

解くのが遅くて実質WA。 環境を更新後の初のするめだったらしくGreedのpathが通ってなくて手間取ってたのが悪いんだよきっと。

solution

Each possible indices to split, do simple DP. $O(N^3)$.

implementation

#include <bits/stdc++.h>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
class RepeatString { public: int minimalModify(string s); };

const int inf = 1e9+7;
int RepeatString::minimalModify(string s) {
    int n = s.length();
    int ans = (n+1)/2;
    repeat (sep,n+1) {
        string a = s.substr(0, sep);
        string b = s.substr(sep, string::npos);
        int al = a.length();
        int bl = b.length();
        vector<vector<int> > dp(al+1, vector<int>(bl+1, inf));
        dp[0][0] = 0;
        repeat (i,al+1) {
            repeat (j,bl+1) {
                if (j < bl) setmin(dp[i][j+1], dp[i][j] + 1); // insert
                if (i < al) setmin(dp[i+1][j], dp[i][j] + 1); // remove
                if (i < al and j < bl) setmin(dp[i+1][j+1], dp[i][j] + (a[i] != b[j])); // replace
            }
        }
        setmin(ans, dp[al][bl]);
    }
    return ans;
}