이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
//dp cost of building S[a, b] with S[c, d] in clipboard
int n;
cin >> n;
string s;
cin >> s;
int A, B, C;
cin >> A >> B >> C;
int maxCost = max({A, B, C}) * n;
// vector<vector<vvi>> dp(n, vector<vvi>(n, vvi(n + 1, vi(n + 1, max({A, B, C}) * n))));
// loop(i, n) {
// dp[i][i][n][n] = A;
// }
// for (int i = 1; i <= 2 * n; i++) {
// }
// 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);
// }
// }
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 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... |