POJ 3661(贝茜晨练）

经典Dp，果断记忆化……

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<functional>
using namespace std;
#define MAXN 10000 + 10
#define MAXM 500 + 10
int f[MAXN][MAXM],n,m,d[MAXN];
int dfs(int i,int j)
{
  if (i==0) return 0;
  if (f[i][j]) return f[i][j];
  if (i&&!j) f[i][j]=dfs(i-1,0);
  if (j)
     f[i][j]=dfs(i-1,j-1)+d[i];
  else
  {
    for (int k=min(i,m);k>0;k--)
    {
            f[i][j]=max(f[i][j],dfs(i-k,k));
    }
  }
  return f[i][j];
}
int main()
{
//  freopen("running.in","r",stdin);
  memset(f,0,sizeof(f));
  scanf("%d%d",&n,&m);
  for (int i=1;i<=n;i++) scanf("%d",&d[i]);

  printf("%d\n",dfs(n,0));

//  while (1); 
  return 0;
}