dp—— [Usaco2007 Jan]Running贝茜的晨练计划

转移方程：

add[i]放到i的和

f[i]到i为止最大值

f[i]=max(f[i],f[i-2*j]+add[i-j]-add[i-2*j]);

DP不是很会啊，加油。。。

#include<stdio.h>

int f[10009];
int add[10009];

int max(int a,int b)
{if(a>b)return a;
else return b;
}

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int i,j;
        add[0]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&add[i]);
            add[i]+=add[i-1];
            f[i]=0;
        }

        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                if(i-2*j<0)break;
                f[i]=max(f[i],f[i-2*j]+add[i-j]-add[i-2*j]);
            }
            f[i]=max(f[i],f[i-1]);
        }

        printf("%d\n",f[n]);
    }
}