Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define NguyenDangQuan the_author
- #define my_heart love_you_to_the_moon_and_back
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using ld = long double;
- using ull = unsigned long long;
- bool typetest;
- inline void fastIOfileinput()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- typetest = 0;
- }
- const int N = 3e5 + 5;
- int n, k;
- ll a[N], dp[N][4][10][10];
- const ll Inf = 1e18;
- void Read()
- {
- cin >> n >> k;
- for (int i = 1; i <= n; ++i)
- cin >> a[i];
- if (n < 3)
- {
- cout << *min_element(a + 1, a + n + 1);
- exit(0);
- }
- }
- void Minimize(ll &x, ll y)
- {
- if (x > y)
- x = y;
- }
- /// j : cho
- /// t : nhan
- void Do_Optimization()
- {
- for (int i = 1; i <= n; ++i)
- for (int j = 0; j <= k; ++j)
- for (int t = 0; t <= k; ++t)
- {
- /// 00 = 0
- Minimize(dp[i][0][j][t], min(dp[i - 1][2][j][t], j > 0 ? dp[i - 1][2][j - 1][t] + a[i] : Inf));
- /// 01 = 1
- Minimize(dp[i][1][j][t], min(dp[i - 1][0][j][t] + a[i], t > 0 ? dp[i - 1][0][j][t - 1] : Inf));
- Minimize(dp[i][1][j][t], min(dp[i - 1][2][j][t] + a[i], t > 0 ? dp[i - 1][2][j][t - 1] : Inf));
- /// 10 = 2
- Minimize(dp[i][2][j][t], min(dp[i - 1][1][j][t], j > 0 ? dp[i - 1][1][j - 1][t] + a[i] : Inf));
- Minimize(dp[i][2][j][t], min(dp[i - 1][3][j][t], j > 0 ? dp[i - 1][3][j - 1][t] + a[i] : Inf));
- /// 11 = 3
- Minimize(dp[i][3][j][t], min(dp[i - 1][1][j][t] + a[i], t > 0 ? dp[i - 1][1][j][t - 1] : Inf));
- Minimize(dp[i][3][j][t], min(dp[i - 1][3][j][t] + a[i], t > 0 ? dp[i - 1][3][j][t - 1] : Inf));
- }
- }
- void Reset()
- {
- fill_n(&dp[0][0][0][0], N * 10 * 10 * 4, Inf);
- }
- void Solve()
- {
- ll ans = Inf;
- Reset();
- dp[0][0][0][0] = dp[0][2][0][0] = 0;
- Do_Optimization();
- for (int i = 0; i <= k; ++i)
- ans = min(ans, min(min(dp[n][0][i][i], dp[n][3][i][i]), min(dp[n][1][i][i], dp[n][2][i][i])));
- cout << ans;
- }
- int32_t main()
- {
- fastIOfileinput();
- if (typetest)
- {
- int t;
- cin >> t;
- while (t--)
- {
- Read();
- Solve();
- }
- }
- else
- {
- Read();
- Solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement