제출 #1054808

#제출 시각아이디문제언어결과실행 시간메모리
1054808j_vdd16Copy and Paste 3 (JOI22_copypaste3)C++17
15 / 100
921 ms2097152 KiB
#include <algorithm> #include <bitset> #include <cstdint> #include <cstring> #include <iostream> #include <limits.h> #include <math.h> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <vector> #define int long long #define loop(X, N) for(int X = 0; X < (N); X++) #define all(V) V.begin(), V.end() #define rall(V) V.rbegin(), V.rend() using namespace std; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vector<ii>> vvii; typedef vector<bool> vb; typedef vector<vector<bool>> vvb; typedef uint64_t u64; typedef int64_t i64; int n; string s; int A, B, C; int maxCost; // int cost(int a, int b, int c, int d) { // if (c == d) return (b - a) * A; // int res; // if (a > b) res = cost(a, b - 1, c, d) + A; // else if (a == b) res = cost(a, b, ) // return res; // } vector<vector<vvi>> dp; int& get(int a, int b, int c, int d) { if (a == b) { a = 0; b = 0; } if (c == d) { c = 0; d = 0; } return dp[a][b][c][d]; } signed main() { ios::sync_with_stdio(0); cin.tie(0); //dp cost of building S[a, b] with S[c, d] in clipboard cin >> n; cin >> s; cin >> A >> B >> C; maxCost = max({A, B, C}) * n; /* dp[a][b][c][d] */ // loop(i, n) { // dp[i][i][n][n] = A; // } // for (int i = 1; i <= 2 * n; i++) { // } /* dp[a][b][c][d] dp[a][b][c][d] = min(dp[a][b][c][d], dp[a][b - 1][c][d] + A) dp[0][0][c][d] = min(dp[c][d][a][b] + B) if (s[b-(d-c), b] == s[c, d]) dp[a][b][c][d] = min(dp[a][b][c][d], dp[a][b-(d-c)][c][d] + C) */ dp = vector<vector<vvi>>(n + 1, vector<vvi>(n + 1, vvi(n + 1, vi(n + 1, maxCost)))); dp[0][0][0][0] = 0; //loop(idx, (n + 1)) { loop(c, n + 1) { for (int d = c; d < n + 1; d++) { loop(a, n + 1) { for (int b = a; b < n + 1; b++) { if (b - 1 >= a) get(a, b, c, d) = min(get(a, b, c, d), get(a, b - 1, c, d) + A); if (b - (d - c) >= a && d > c && s.substr(b - (d - c), d - c) == s.substr(c, d - c)) { get(a, b, c, d) = min(get(a, b, c, d), get(a, b - (d - c), c, d) + C); } get(0, 0, a, b) = min(get(0, 0, a, b), get(a, b, c, d) + B); } } } } //} int result = maxCost; loop(c, n + 1) { loop(d, n + 1) { result = min(result, dp[0][n][c][d]); } } cout << result << endl; // map<string, int> clipBoardCost; // clipBoardCost[""] = 0; // loop(i, n) { // clipBoardCost[s.substr(i, 1)] = A + B; // } // for (int sz = 2; sz <= n; sz++) { // loop(i, n) { // string goal = s.substr(i, sz); // string prev = goal; // prev.pop_back(); // clipBoardCost[goal] = min(clipBoardCost[goal], sz * A); // } // } return 0; // vvi cost(n + 1, vi(n + 1, maxCost)); // cost[0][0] = 0; // //cost[0][j] = min(cost[j][i] + B) // //cost[i][j] = min(cost[i - j][j] + C, cost[i - 1][j] + A) // loop(i, n + 1) { // loop(j, n + 1) { // if (i - 1 >= 0) cost[i][j] = min(cost[i][j], cost[i - 1][j] + A); // if (i - j >= 0) cost[i][j] = min(cost[i][j], cost[i - j][j] + C); // cost[0][i] = min(cost[0][i], cost[i][j] + B); // } // } // int result = maxCost; // loop(j, n + 1) { // result = min(result, cost[n][j]); // } // cout << result << endl; // 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...