Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * @file caper.cpp
- * @version 1.0
- * @date 2024-04-03
- *
- * usage:
- * Read from / write to default input.txt and output.txt
- * caper.exe
- * Read from / write to custom files:
- * caper.exe in.txt out.txt
- */
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- void fileIO(int argc, char *argv[]);
- const int INF = 1e5;
- int minMovesToErase(vector<int> v) {
- int n = v.size();
- vector<vector<int>> dp(1+n, vector<int>(1+n));
- v.push_back(0);
- /*
- dp[l][r] is the minimum number of moves to erase the range v[l], v[l+1], ..., v[r-1]
- (excluding r), given that only elements from the same collection as v[r] can remain
- */
- /*
- It can be shown that for any block of values from the same collection that are initially
- consecutive, it can be shown that all optimal solutions will erase them all in one step.
- I use this to slightly simplify the code, though the main concept of the solution does not
- depend on it.
- */
- for (int sz = 1; sz <= n; ++sz) {
- for (int l = 0; l+sz <= n; ++l) {
- int r = l+sz;
- dp[l][r] = INF;
- int canLeave = v[r];
- // case: do not erase the first element
- if (v[l] == canLeave) dp[l][r] = min(dp[l][r], dp[l+1][r]);
- // case: erase the first element
- int firstBlockR = l;
- while (firstBlockR < r && v[firstBlockR] == v[l]) ++firstBlockR;
- // subcase: erase the first element in its own block (if the block size is >= 2)
- if (firstBlockR-l >= 2) dp[l][r] = min(dp[l][r], 1 + dp[firstBlockR][r]);
- // subcase: erase the first element along with another block
- for (int i = firstBlockR, lastDifferent = firstBlockR; i < r; ++i) {
- if (v[i] == v[l] && (i+1 == r || v[i+1] != v[l])) { // a block with from the same collection as v[l] ends at i
- int lastBlockL = lastDifferent+1, lastBlockR = i+1;
- dp[l][r] = min(dp[l][r], 1 + dp[firstBlockR][lastBlockL] + dp[lastBlockR][r]);
- } else if (v[i] != v[l]) lastDifferent = i;
- }
- }
- }
- return dp[0][n];
- }
- int main(int argc, char *argv[]) {
- fileIO(argc, argv); // remove for standard input/output
- int n; cin >> n;
- vector<int> a(n);
- for (int &x : a) cin >> x;
- cout << minMovesToErase(a) << '\n';
- return 0;
- }
- void fileIO(int argc, char *argv[]) {
- const char * in = "input.txt", * out = "output.txt";
- if (argc > 1) in = argv[1];
- if (argc > 2) out = argv[2];
- freopen(in, "r", stdin);
- freopen(out, "w", stdout);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement