时间限制：0.25s
空间限制:4M
题意:
在n（n<=10000）个球中,给若干个球涂色,每个球涂色的代价为Ci,使得任意连续m（m<=100）个球中有至少两个球被涂了色.
Solution：
首先很直接地能想到一个DP的状态转移方程
f[i][j] 代表，当前涂第i个球，且前面最近一个被涂色的球为j的最小代价
f[i][j]=min(f[j][k])+Ci, k>i+1-m
分析这个转移方程的时间复杂度是O（n*m*m）在此题的数据范围中高达10^8
显然我们需要更好的解法
分析上面的方程发现，在计算min（f[j][k]）时，是有重复计算的部分的，
于是想办法减少这个重复的过程。
对于 一个 j，i的范围在 （j+1，j+m-1）
对应k的范围 是（i+1-m+1）~（j-1）
如果我们让i从（j+m-1）倒推至（j+1）
就可以让k从（j-1）变成（i+1-m+1）
min（f[j][k]）需要计算的范围就会依次变大，而且可以递推求出
即可以在O（1）的时间里求出min（f[j][k]）
总的时间复杂度就变成了O（n*m）
再发现空间上不能直接用n*m的数组，加上滚动数组优化就行了
code
#include <iostream>
#include <cstring>
using namespace std;
const int mod = 101;
int n, m;
int c[10009];
//f[i][j]涂当前第i个球,和第i,第j个球的最小代价
//只保留最近的200个;
int f[200][200];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> c[i];
memset (f, 0x3f, sizeof f);
f[1][0]=c[1];
for (int i = 1; i <= m; i++)
for (int j = 1; j < i; j++)
f[i][j] = c[i] + c[j];
for (int j = 2; j < n; j++) {
int tem = 0x3f3f3f3f;
for (int i = j + m - 1; i > j; i--) {
if(i<=m) break;
tem = min (tem, f[j%mod][(i - m)%mod]);
f[i%mod][j%mod] = tem + c[i];
}
}
int ans = 0x7fffffff;
for (int i = n - m + 1; i <= n; i++)
for (int j = i - 1; i - j < m && n - j < m; j--)
ans = min (ans, f[i % mod][j % mod]);
cout << ans;
return 0;
}