题目的意思是给出含有n(n<=10000)个数字的序列，从序列中选取m(m<=100)个数字，任意两个相邻的数字的位置差不能小于k，求m个数字的最大值。

考试的时候没有想到用动态规划，只想到了一种贪心，每次选取最大的那个数字，查看如果选取它是不是和已经选取的发生冲突，如果不冲突，则选取，否则继续下一个最大的数字。考试时不是没有向动态规划的方向考虑过，而是想到如果定义d[i][j]为第i次选取第j个数字获得的最大值，那么算法的时间复杂度是O(mn^2)，肯定超时！

考完试仔细思考，如果定义d[i][j]为第i次选取前j个数字获得的最大值，时间复杂度不就是O(mn)了吗！怎么考试的时候没有想到！这样一来，状态转移方程如下：d[i][j]=max(d[i][j-1]，d[i-1][j-k]+a[j])。对于每一个确定的i，j都有一个取值范围，(i-1)*k+1<=j<=n-(m-i)*k。同时需要注意(i-1)*k+1==j时，必须要选取当前数字，因为需要在编号1—j的数字中选择i个数字。使用滚动数组的技巧，可以把空间复杂度优化到O(n)。

我的代码如下：

#include<stdio.h>
#define max(a,b) (a>b?a:b)
long n,m,k,i,j,a[10088],d[2][10088]={0};
int main()
{
    FILE *fin,*fout;
    fin=fopen("bright.in","r");
    fscanf(fin,"%ld%ld%ld",&n,&m,&k);
    for(i=1;i<=n;i++)
      fscanf(fin,"%ld",&a[i]);
    fclose(fin);
    // Read In
    d[0][1]=a[1];
    for(i=2;i<=n;i++)
      d[0][i]=max(a[i],d[0][i-1]);
    for(i=2;i<=m;i++)
      for(j=(i-1)*k+1;j<=n-(m-i)*k;j++)
        if(j==(i-1)*k+1) d[(i+1)%2][j]=d[i%2][j-k]+a[j];
        else d[(i+1)%2][j]=max(d[i%2][j-k]+a[j],d[(i+1)%2][j-1]);
    // DP
    fout=fopen("bright.out","w");
    fprintf(fout,"%ld\n",d[(m+1)%2][n]);
    fclose(fout);
return 0;
}