題目的意思是給出含有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;
}