有n件物品，每件物品都有一个花费，要求每m个中必须至少选2个，求最小花费

题目

#include<bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize(2)
const int maxn = 2e4 + 5, maxm = 2e3 + 5, inf = 1e9;
int a[maxn];
int f[maxm][maxm];//f[i][j]表示选了第i个，上一个选的是第i-j个（每m个中选2个等价于选的第k个和第k-2个的距离<=m
int pre_min[maxm][maxm];//前缀最小值
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;
}
void write(int x)
{if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');return;
}
void solve(){int n, i, j, m;//cin >> n >> m;n = read(), m = read();for(i = 1; i <= n; i++){//cin >> a[i];a[i] = read();}a[++n] = 0;//在末尾加一个0，表示这个人必选，方便后面统计答案int res = inf;for(i = 1; i <= m; i++){for(j = 0; j <= m; j++){f[i][j] = pre_min[i][j] = inf;}for(j = 1; j < i; j++){f[i][j] = a[i] + a[i - j];pre_min[i][j] = min(pre_min[i][j - 1], f[i][j]);}}for(i = m + 1; i <= n; i++){int cur = (i - 1) % m + 1;for(j = 1; j < m; j++){int last = (i - j - 1) % m + 1;f[cur][j] = pre_min[last][m - j] + a[i];pre_min[cur][j] = min(pre_min[cur][j - 1], f[cur][j]);}}for(j = 1; j < m; j++){res = min(res, f[(n - 1) % m + 1][j]);}//cout << res << '\n';write(res);putchar('\n');// for(i = 1; i <= m; i++){// 	for(j = 0; j <= m; j++){// 		f[i][j] = inf;// 		pre_min[i][j] = inf;// 	}// }// f[1][0] = a[1];// f[1][1] = a[1];// const int mod = m;// pre_min[1][0] = pre_min[1][1] = a[1];// int res = inf;// //cout << pre_min[0][0] << '\n';// for(i = 2; i <= n; i++){//一次用滚动数组更新完不好搞，因为pre[0][k] = 0,会影响后面的更新// 	int cur = i % mod;// 	for(j = 1; j <= m - 1 && i - j >= 0; j++){// 		int last = (i - j) % mod;// 		int tmp = min(i - j, m - j);// 		f[cur][j] = pre_min[last][tmp] + a[i];// 		// if(i == 2 && j == 2){// 		// 	cout << "test";// 		// 	cout << (i - j - 1 + m) % m + 1 << ' ' << tmp << ' ' << pre_min[(i - j - 1 + m) % m + 1][tmp] << '\n';// 		// }// 		pre_min[cur][j] = min(pre_min[cur][j - 1], f[cur][j]);// 		//res = min(res, f[i][j]);// 		cout << i << ' ' << j << ' ' << tmp << ' ' << f[cur][j] << ' ' << pre_min[cur][j] << '\n';// 	}// }// for(i = 1; i <= m; i++){// 	res = min(res, f[n % mod][i]);// }// cout << res << '\n';}
signed main(){// ios::sync_with_stdio(0);// cin.tie(0);int T;//cin >> T;T = read();while(T--){solve();}return 0;
}