Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 610;
- const int MAXK = 60;
- int dp[MAXN][MAXK];
- int s[MAXN][MAXN];
- int last[MAXN][MAXK];
- int N, K;
- int cost(int ini, int fim)
- {
- return s[fim][N] - s[fim][fim] - s[ini-1][N] + s[ini-1][fim];
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cin >> N >> K;
- for (int i = 1; i < N; i++)
- {
- for (int j = i+1; j <= N; j++)
- {
- cin >> s[i][j];
- }
- }
- for (int i = 1; i <= N; i++)
- {
- for (int j = 1; j <= N; j++)
- {
- s[i][j] += s[i][j-1] + s[i-1][j];
- s[i][j] -= s[i-1][j-1];
- // cerr << s[i][j] << " ";
- }
- // cerr << '\n';
- }
- for (int j = 1; j <= K; j++)
- {
- for (int i = 1; i < N; i++)
- {
- if (j == 1) {dp[i][j] = s[i][N] - s[i][i]; continue;}
- for (int k = 1; k < i; k++)
- {
- // cerr << "||" << cost(k+1, i) << '\n';
- if (dp[k][j-1] + cost(k+1, i) > dp[i][j])
- {
- last[i][j] = k;
- dp[i][j] = dp[k][j-1] + cost(k+1, i);
- }
- }
- }
- }
- // for (int i = 1; i < N; i++) cerr << dp[i][K] << " ";
- // cerr << '\n';
- int x = 0;
- for (int i = 1; i < N; i++)
- {
- if (dp[i][K] > dp[x][K]) x = i;
- }
- vector<int> resp;
- while (K)
- {
- resp.push_back(x);
- x = last[x][K];
- K--;
- }
- reverse(resp.begin(), resp.end());
- // resp.pop_back();
- for (auto x : resp) cout << x << " ";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement