이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define cerr if(false)cerr
const ll MAX_N = 2510;
ll n, a, b, c;
string str;
ll dp[MAX_N][MAX_N][2];
ll ind[MAX_N][MAX_N], cnt;
const ll LOG = 14;
ll par[MAX_N * MAX_N][LOG], start[MAX_N * MAX_N], d[MAX_N * MAX_N];
vector<ll> g[MAX_N * MAX_N];
void dfs(ll x, ll p) {
par[x][0] = p;
for(ll i = 1; i < LOG; i ++) {
par[x][i] = par[par[x][i - 1]][i - 1];
}
d[x] = d[p] + 1;
for(const auto it : g[x]) {
dfs(it, x);
}
}
ll lft(ll l, ll r, ll len) {
ll id = ind[r - len + 1][len];
ll ret = d[id];
for(ll i = LOG - 1; i >= 0; i --) {
if(start[par[id][i]] >= l) {
id = par[id][i];
}
}
return ret - d[id] + 1;
}
ll solve(ll l, ll r, bool clip) {
if(!clip) { return (r - l + 1) * a; }
if(dp[l][r][clip] != -1) { return dp[l][r][clip]; }
if(l == r) { return a; }
ll &ans = dp[l][r][clip];
ans = (r - l + 1) * a;
ans = min(ans, solve(l, r - 1, true) + a);
ans = min(ans, solve(l, r - 1, false) + a);
for(ll len = 1; len <= (r - l + 1); len ++) if(d[ind[r - len + 1][len]] != d[0] + 1) {
ll cnt = lft(l, r, len);
ll total =
solve(r - len + 1, r, true) + b +
cnt * c + (r - l + 1 - cnt * len) * a;
ans = min(ans, total);
}
return ans;
}
const ll mod1 = 1e9 + 7, mod2 = 2e9 + 9;
const ll base1 = 27, base2 = 37;
ll state[MAX_N];
signed main() {
cin >> n >> str >> a >> b >> c;
for(ll len = 1; len <= n; len ++) {
ll hsh1 = 0, hsh2 = 0;
ll pw1 = 1, pw2 = 1;
for(ll i = 0; i < len; i ++) {
ll now = str[i] - 'a' + 1;
hsh1 = (hsh1 * base1 + now) % mod1;
hsh2 = (hsh2 * base2 + now) % mod2;
if(i != 0) {
pw1 = (pw1 * base1) % mod1;
pw2 = (pw2 * base2) % mod2;
}
}
state[0] = hsh1 + hsh2 * mod1;
for(ll i = 1; i + len - 1 < n; i ++) {
ll now = str[i + len - 1] - 'a' + 1;
hsh1 = (
(hsh1 - pw1 * (ll)(str[i - 1] - 'a' + 1ll))
% mod1 * base1 + now
) % mod1;
hsh2 = (
(hsh2 - pw2 * (ll)(str[i - 1] - 'a' + 1ll))
% mod2 * base2 + now
) % mod2;
state[i] = hsh1 + hsh2 * mod1;
}
map<ll, ll> mp;
for(ll i = 0; i + len - 1 < n; i ++) {
ind[i][len] = ++ cnt;
start[cnt] = i;
if(i - len >= 0) {
mp[state[i - len]] = ind[i - len][len];
}
g[mp[state[i]]].push_back(ind[i][len]);
}
}
start[0] = -mod1;
dfs(0, 0);
for(ll i = 0; i < n; i ++) {
for(ll j = 0; j < n; j ++) {
dp[i][j][0] = dp[i][j][1] = -1;
}
}
cout << solve(0, n - 1, true) << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |