題目的意思是給出含有n(n<=10000)個數(shù)字的序列，從序列中選取m(m<=100)個數(shù)字，任意兩個相鄰的數(shù)字的位置差不能小于k，求m個數(shù)字的最大值。

考試的時候沒有想到用動態(tài)規(guī)劃，只想到了一種貪心，每次選取最大的那個數(shù)字，查看如果選取它是不是和已經(jīng)選取的發(fā)生沖突，如果不沖突，則選取，否則繼續(xù)下一個最大的數(shù)字。考試時不是沒有向動態(tài)規(guī)劃的方向考慮過，而是想到如果定義d[i][j]為第i次選取第j個數(shù)字獲得的最大值，那么算法的時間復雜度是O(mn^2)，肯定超時！

考完試仔細思考，如果定義d[i][j]為第i次選取前j個數(shù)字獲得的最大值，時間復雜度不就是O(mn)了嗎！怎么考試的時候沒有想到！這樣一來，狀態(tài)轉(zhuǎn)移方程如下：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時，必須要選取當前數(shù)字，因為需要在編號1—j的數(shù)字中選擇i個數(shù)字。使用滾動數(shù)組的技巧，可以把空間復雜度優(yōu)化到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;
}