标签：min int rep else TheKingsArmyDiv1 chkmi dp

Topcoder #区间dp

考虑 \(dp_{l,r,3}\) 表示当前考虑区间 \([l,r]\) ，上面一行全部 \(H\) 的最小代价，下面一行全部 \(H\) 的最小代价，上下都 \(H\) 的最小代价

转移考虑每次将两段拼起来，或者从现有的拓展一个

貌似有贪心做法，不太会喵~~~

// Author: xiaruize
const int N = 2e2 + 10;

int n;
char s[3][N];
int dp[N][N][3];

void chkmi(int &x, int y)
{
    if (y < x)
        x = y;
}

void solve()
{
    cin >> n;
    cin >> (s[1] + 1) >> (s[2] + 1);
    n = strlen(s[1] + 1);
    mms(dp, 0x3f);
    rep(i, 1, n)
    {
        if (s[1][i] == 'H')
            dp[i][i][0] = 0;
        else if (s[2][i] == 'H')
            dp[i][i][0] = 1;
        if (s[2][i] == 'H')
            dp[i][i][1] = 0;
        else if (s[1][i] == 'H')
            dp[i][i][1] = 1;
        if (s[1][i] == 'H' && s[2][i] == 'H')
            dp[i][i][2] = 0;
        else if (s[1][i] == 'H' || s[2][i] == 'H')
            dp[i][i][2] = 1;
    }
    rep(len, 2, n)
    {
        rep(l, 1, n - len + 1)
        {
            int r = l + len - 1;
            chkmi(dp[l][r][0], min(dp[l][r - 1][0] + 1, dp[l + 1][r][0] + 1));
            chkmi(dp[l][r][1], min({dp[l][r - 1][1] + 1, dp[l + 1][r][1] + 1}));
            chkmi(dp[l][r][2], min({dp[l][r - 1][2] + 1, dp[l + 1][r][2] + 1}));
            rep(k, l, r - 1)
            {
                chkmi(dp[l][r][0], min({dp[l][k][0], dp[l][k][1] + 1, dp[l][k][2]}) + min({dp[k + 1][r][0], dp[k + 1][r][1] + 1, dp[k + 1][r][2]}));
                chkmi(dp[l][r][1], min({dp[l][k][1], dp[l][k][0] + 1, dp[l][k][2]}) + min({dp[k + 1][r][1], dp[k + 1][r][0] + 1, dp[k + 1][r][2]}));
                chkmi(dp[l][r][2], min({dp[l][k][0] + 1, dp[l][k][1] + 1, dp[l][k][2]}) + min({dp[k + 1][r][0] + 1, dp[k + 1][r][1] + 1, dp[k + 1][r][2]}));
            }
            chkmi(dp[l][r][2], min(dp[l][r][0], dp[l][r][1]) + 1);
        }
    }
    if (dp[1][n][2] > n)
        cout << "-1" << endl;
    else
        cout << dp[1][n][2] << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
#ifndef ONLINE_JUDGE
    cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
    cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
    return 0;
}

标签：min,int,rep,else,TheKingsArmyDiv1,chkmi,dp
From： https://www.cnblogs.com/xiaruize/p/18136777