제출 #1167540

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167540		fryingduc	Copy and Paste 3 (JOI22_copypaste3)	C++20	15 / 100	388 ms	215072 KiB

copypaste3

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2005;
int n;
string s;
int a, b, c;
long long f[maxn][maxn];
vector<int> ft[maxn];
vector<pair<int, int>> cand[maxn][maxn];

vector<int> z_function(string s) {
  int n = s.length();
  vector<int> z(n);
  for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i <= r)
      z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < n && s[z[i]] == s[i + z[i]])
      ++z[i];
    if (i + z[i] - 1 > r) {
      l = i;
      r = i + z[i] - 1;
    }
  }
  return z;
}

void mnz(long long &x, long long y) {
  x = min(x, y);
}

void solve() {
  cin >> n >> s >> a >> b >> c;
  for (int i = 0; i < n; ++i) {
    string v = s.substr(i, n - i);
    vector<int> z = z_function(v);
    ft[i].resize(n - i + 1, -1);
    for (int j = n - i - 1; j >= 0; --j) {
      if (j >= z[j]) {
        ft[i][z[j]] = j;
      } else {
        ft[i][j] = j;
      }
    }
    for (int j = n - i - 1; j >= 0; --j) {
      if (ft[i][j] == -1 || ft[i][j] > ft[i][j + 1]) {
        if (ft[i][j + 1] != -1) ft[i][j] = ft[i][j + 1];
      }
    }
//    debug(i, ft[i]);
  }
  for (int l = n - 1; l >= 0; --l) {
    for (int i = l; i < n; ++i) {
      int prf = i - l + 1;
      if (ft[l][prf] == -1) continue;
      int cur = l + ft[l][prf], cnt = 1;
//      debug(l, prf, cur);
      long long cost = f[l][i] + b;
      while (cur < n - l + 1 and cur != -1) {
        ++cnt;
        cand[l][cur + prf - 1].emplace_back(prf, cnt);
        if (ft[cur][prf] == -1) break;
        cur = cur + ft[cur][prf];
      }
    }
  }
  for (int l = n - 1; l >= 0; --l) {
    for (int r = l; r < n; ++r) {
      f[l][r] = min(f[l][r - 1], f[l + 1][r]) + a;
      for (auto [len, cnt] : cand[l][r]) {
        long long cost = f[l][l + len - 1] + b;
        mnz(f[l][r], cost + 1ll * cnt * c + 1ll * (r - l + 1 - cnt * len) * a);
//        debug(l, r, len, cnt, f[l][r]);
      }
//      debug(l, r, f[l][r]);
    }
  }
  cout << f[0][n - 1];
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}
/*
7
abbabaa
1000000000
100000
10000000
*/

• Subtask 1: 1 / 1
• Subtask 2: 0 / 5
• Subtask 3: 14 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 32
• Subtask 6: 0 / 38