找朋友2
题意
给出 \(n\) 个数，要求每连续 \(m\) 选出至少两个数，求出选出数和的最小值。
思路
定义 \(dp_{i,j}\) 表示考虑前 \(i\) 个人，第 \(i\) 个人和第 \(i-j\) 个人必选的和的最小值。
\[dp_{i,j} = \min_{j+k\le m} \left \{ dp_{i-j,k} \} \right. +a_i \]若 \(j+k>m\)，\([i-m+1,i]\) 这个区间就只选了一个数，不合法。
时间复杂度：\(O(nm^2)\)，空间复杂度：\(O(nm)\)，均不能通过，考虑优化。
发现 \(\min\) 中的方程是前缀最小值的形式，转移时维护一下。
发现当前有用的状态只有 \([i,i-m+1]\) 着 \(m\) 个，只用开一个 \(O(m^2)\) 的数组，将下标 \(\bmod m\) 即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 5;
const int M = 2e3 + 5;
int n, m, a[N], dp[M][M], Min[M][M], ans;
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int j = 0; j <= m; j ++) {
dp[0][j] = Min[0][j] = 0;
}
for (int i = 1; i <= m; i ++) {
for (int j = 0; j <= m; j ++)
dp[i][j] = Min[i][j] = 0x3f3f3f3f;
}
// memset(dp, 0x3f, sizeof(dp));
// memset(Min, 0x3f, sizeof(Min));
ans = 0x3f3f3f3f;
// memset(dp[0], 0, sizeof(dp[0]));
// memset(Min[0], 0, sizeof(Min[0]));
for (int i = 1; i <= n; i ++) {
int now = i % m;
for (int j = 0; j <= m; j ++)
Min[now][j] = 0x3f3f3f3f, dp[now][j] = 0x3f3f3f3f;
for (int j = 1; j <= min(i, m); j ++) {
// int Min = 0x3f3f3f3f;
// for (int k = 1; k <= m - j; k ++) {
// Min = min(Min, dp[i - j][k]);
// }
// dp[i][j] = Min + a[i];
int pre = (i - j + m) % m;
dp[now][j] = Min[pre][m - j] + a[i];
Min[now][j] = min(Min[now][j - 1], dp[now][j]);
if (i >= n - m + 1 + j)
ans = min(ans, dp[now][j]);
// cout << i << " " << j << " " << dp[i][j] << "\n";
}
for (int j = 1; j <= m; j ++)
Min[now][j] = min(Min[now][j], Min[now][j - 1]);
}
cout << ans << "\n";
}
int main() {
freopen("gaoj.in", "r", stdin);
freopen("gaoj.out", "w", stdout);
int Case;
cin >> Case;
while (Case --)
solve();
return 0;
}