2017-2018 ACM-ICPC Southeast Regional Contest (Div. 1) - Ducks in a Row

問題リンク (コンテストページです)

解説

文字が1つ以上区間を開けて、個作るわけですから、ならば作ることはできないので、-1を出力します。

以下 であるものとします。

この時、なわけですから、が間に合うということに注意しましょう。

そうすると

あとはこう定義できれば、愚直にDPを遷移させるだけです！

注意点として、 の状態から になるときに、が1つふえます。

DPの値は の時は、反転させてもさせなくても増えません(連続した区間をとって、反転することができるからです)

の時は、反転させる場合に1増えます。(反転させるとl == 1になることに注意しましょう)

あとは実装をみていただければ解けると思います！

提出コード

#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int inf = 1000000007;
constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353LL;
const long double PI = acos((long double)(-1));
using namespace std;
typedef unsigned long long ull;
typedef long long ll;


void init(vector<vector<vector<int>>>& a) {
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < a[i].size(); j++) {
            for (int k = 0; k < a[i][j].size(); k++) {
                a[i][j][k] = inf;
            }
        }
    }
}
int main()
{
    
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    

    int n, k; cin >> n >> k;
    string s; cin >> s;
    int sz = s.size();
    if (n * k + k - 1 > sz) {
        puts("-1");
        return 0;
    }
    vector<vector<vector<vector<int>>>> dp(2, vector<vector<vector<int>>>(n + 1, vector<vector<int>>(k + 1, vector<int>(2, inf))));
    dp[0][0][0][0] = 0;
    int cur = 0;
    int next = 1;
    for (int i = 0; i < s.size(); i++) {
        init(dp[next]);
        for (int len = 0; len <= n; len++) {
            for (int cnt = 0; cnt <= k; cnt++) {
                int mn1 = min(dp[cur][len][cnt][0], dp[cur][len][cnt][1]);
                int mn2 = min(dp[cur][len][cnt][0] + 1, dp[cur][len][cnt][1]);
                if (s[i] == 'D') {
                    if (len == n - 1) {
                        chmin(dp[next][n][min(cnt + 1, k)][0], mn1);
                    }
                    else {
                        chmin(dp[next][min(len + 1, n)][cnt][0], mn1);
                    }
                    chmin(dp[next][0][cnt][1], mn2);
                }
                else {
                    if (len == n - 1) {
                        chmin(dp[next][n][min(cnt + 1, k)][1], mn2);
                    }
                    else {
                        chmin(dp[next][min(len + 1, n)][cnt][1], mn2);
                    }
                    chmin(dp[next][0][cnt][0], mn1);
                }
            }
        }
        swap(next, cur);
    }
    int res = inf;
    for (int i = 0; i <= n; i++) for (int j = 0; j < 2; j++) chmin(res, dp[cur][i][k][j]);
    if (res == inf) res = -1;
    cout << res << endl;
    return 0;
}