제출 #1060936

#제출 시각아이디문제언어결과실행 시간메모리
1060936thinknoexitCopy and Paste 3 (JOI22_copypaste3)C++17
30 / 100
10 ms31660 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; char s[2505]; int qs[202][202], cnt[202][202][202]; ll dp[202][202]; ll A, B, C; int main() { cin.tie(nullptr)->sync_with_stdio(false); int n; cin >> n; bool ch = 1; for (int i = 1;i <= n;i++) { cin >> s[i]; ch &= s[i] == 'a'; } if (ch) { vector<ll> dp(n + 2, 0); ll A, B, C; cin >> A >> B >> C; for (int i = 1;i <= n;i++) { dp[i] = dp[i - 1] + A; for (int j = 1;j < i;j++) { dp[i] = min(dp[i], (dp[j] + B) + A * (i % j) + C * (i / j)); } } cout << dp[n] << '\n'; return 0; } for (int i = 1;i <= n;i++) { for (int j = 1;i + j <= n;j++) { qs[i][j] = s[i] == s[i + j]; } for (int j = 1;j <= n;j++) { qs[i][j] += qs[i - 1][j]; } } for (int i = 1;i <= n;i++) { for (int j = i;j <= n;j++) { int r = j - i + 1; cnt[i][j][j] = 1; for (int k = j + 1;k <= n;k++) { cnt[i][j][k] = cnt[i][j][k - 1]; // x = k - j int x = k - j; if (qs[j][x] - qs[i - 1][x] == r) cnt[i][j][k] = max(cnt[i][j][k], cnt[i][j][k - r] + 1); } } } cin >> A >> B >> C; for (int i = 1;i <= n;i++) dp[i][i] = A; for (int k = 1;k < n;k++) { for (int i = 1;i <= n - k;i++) { int j = i + k; dp[i][j] = (k + 1) * A; dp[i][j] = min(dp[i][j], A + dp[i + 1][j]); dp[i][j] = min(dp[i][j], dp[i][j - 1] + A); for (int l = 0;l < k;l++) { int c = cnt[i][i + l][j]; ll val = A * (k + 1 - c * (l + 1)); val += dp[i][i + l] + B; val += C * c; dp[i][j] = min(dp[i][j], val); } } } // calculate cost to make X = s[l...r] cout << dp[1][n] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...