Open2022/01/02にコメント追加2

動的計画法学習に関する雑記

C++

競技プログラミング

ピン留めされたアイテム

log5

dpで詰まるたびに更新すると思われる

log5

こう解いたが、答えが合わない...

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()

const long long MOD = 1000000007;
struct mint { 
// https://gist.github.com/judau/be614592846a40341de73a81d69ddcf4
}

void solve(std::string S){
    const string x = "chokudai";
    vector<vector<mint>> dp(S.size() + 1, {1,0,0,0,0,0,0,0,0});
    rep(i, S.size()) {
        if (i == 0) continue;
        rep(j, 9) {
            mint buf = dp[i][j];
            if (S[i + 1] == x[j] && j > 0) {
                buf += dp[i][j - 1];
            }
            dp[i + 1][j] = buf;
        }
    }
    cout << (dp[S.size()][8]) << endl;
}

int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}

よく見るとループ数とかいろいろおかしいので直したバージョン２(solveのみ）

void solve(std::string S){
    const string x = "chokudai";
    vector<vector<mint>> dp(S.size() + 1, {1,0,0,0,0,0,0,0,0});
    rep(i, S.size()) {
        rep(j, 9) {
            mint buf = dp[i][j];
            if (S[i + 1] == x[j] && j > 0) {
                buf += dp[i][j - 1];
            }
            dp[i + 1][j] = buf;
        }
    }
    cout << (dp[S.size()][8]) << endl;
}

正解

jも +1 した値を埋めるようにしたら通った

void solve(std::string S){
    const string x = "chokudai";
    vector<vector<mint>> dp(S.size() + 1, {1,0,0,0,0,0,0,0,0});
    rep(i, S.size()) {
        rep(j, 8) {
            mint buf = dp[i][j + 1];
            if (S[i] == x[j]) {
                buf += dp[i][j];
            }
            dp[i + 1][j + 1] = buf;
        }
    }
    cout << (dp[S.size()][8]) << endl;
}