题解：P15148 [SWERC 2024] Divine Gifting
前言
题目传送门
思路讲解
我们简单思考一下就可以知道，这题输入顺序对结果没有影响，所以排序。
我们考虑用动态规划做，维护 \(dp\) 数组。
\(dp[i][o]\) 表示前 \(i\) 个物品用 \(o\) 天的最优解。
每次美剧前 \(j\) 个物品在 \(o-1\) 天的时间内送掉，剩余的就像你的假期作业一样拖到最后。
AC Code
#include <bits/stdc++.h>
#define int long long int
#define MAXN 5010
#define inf 1000000000000000000
using namespace std;
vector<vector<int> > dp(MAXN, vector<int>(25, inf));
int n, k, sum[MAXN][MAXN];
vector<int> a(MAXN);
inline void init()
{for (int r = n; r >= 1; --r){for (int l = r; l >= 1; --l){sum[l][r] = sum[l + 1][r] + abs((a[r] - a[l]) * (a[r] - a[l]));}}
}
signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin >> n >> k;for (int i = 1; i <= n; i++){cin >> a[i];}vector<pair<int, int>> cnt(n + 1);for (int i = 1; i <= n; i++){cnt[i].first = a[i], cnt[i].second = i;}sort(cnt.begin() + 1, cnt.begin() + 1 + n);sort(a.begin() + 1, a.begin() + n + 1);init();dp[0][0] = 0;for (int i = 1; i <= n; i++){for (int j = 0; j < i; j++){for (int o = k; o >= 1; o--){dp[i][o] = min(dp[i][o], dp[j][o - 1] + sum[j + 1][i]);}}}vector<int> ans;ans.push_back(n);array<int, 3> now;now = {n, min(n, k), dp[n][min(n, k)]};for (int i = k; i >= 1; i--){for (int j = 1; j <= now[0]; j++){if (now[2] - dp[j][i - 1] == sum[j + 1][now[0]]){now[0] = j, now[1]--, now[2] = dp[j][i - 1];ans.push_back(j);break;}}}reverse(ans.begin(), ans.end());int no = 0;vector<int> res(n + 10);for (int i = 1; i <= n; i++){if (i <= ans[no])res[cnt[i].second] = a[ans[no]];if (i == ans[no])no++;}for (int i = 1; i <= n; i++){cout << res[i] << ' ';}return 0;
}