给出n个白球，每个球有一个涂色的费用，要求任意连续m个球中至少有两个黑球，求最少的涂色费用。
由于连续m个球中至少有两个黑球，我们不难得到递推式f(i,j) = min{ f(j,k) | i > j > k >= i-m} + c[i] ，表示当前给第i个球涂色，上一个给第j个球涂色的最小费用。这个递推式的时间复杂度为O(N*M^2)，由于SGU大多数都是卡时间的神题，我们为了追求更高效的算法，可以进行优化。
在求f[i][j]和f[i+1][j]的时候，我们向前找的f[j][k]有很多的重复操作，因此可以从这里下手进行优化。
参考题解：
如果我们把j的值固定，也就是最外层循环为j，那么i的取值范围为 j+1 到 j+m-1，相应的k的取值范围为 j-m+1 到 j-1 (个人觉得题解中写的k的取值范围写得有点问题，这里改了过来)
如果我们在计算f[i][j]的时候倒推i，那么min(f[j][k])需要计算的范围就会依次变大，而且可以递推求出，个人觉得这里最难理解。
即可以在O(1)的时间内求出min(f[j][k])，，时间复杂度变为O(n*m)
#include<cstdio>#include<cstring>#include<iostream>#define MAXN 10005#define mod 101using namespace std;int n,m;int c[MAXN];int f[200][200];int main(){memset(f,0x3f,sizeof f);scanf("%d%d",&n,&m);for(int i = 1; i <= n; i++)scanf("%d",&c[i]);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 minn = 0x3f3f3f3f;for(int i = j+m-1; i > j&&i > m; i–){minn = min(minn,f[j%mod][(i-m)%mod]);//寻找最小的f[j][k]，个人认为这一点最难理解f[i%mod][j%mod] = minn + c[i];}}int ans = 0x3f3f3f3f;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]);printf("%d\n",ans);}
版权声明：本文为博主原创文章，未经博主允许不得转载。
人的价值，在遭受诱-惑的一瞬间被决定
