Sgu/183

/by Logic
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=10050,maxs=300,maxm=120,mod=200,big=500000000;
int n,m,c[maxn],f[maxs][maxm],ans=big;
int main()
{
#ifndef ONLINE_JUDGE
	freopen("data.in","r",stdin);
#endif
	int i,j,k;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
		scanf("%d",&c[i]);
	c[n+1]=0;
	for(i=1;i<m;i++)
		f[i][i]=c[i];
	for(i=1;i<=n+1;i++)
		for(j=max(1,i-m+1);j<i;j++)
		{
			f[i%mod][i-j]=big;
			for(k=max(0,i-m);k<j;k++)
				f[i%mod][i-j]=min(f[i%mod][i-j],f[j%mod][j-k]+c[i]);
		}
	//for(i=1;i<=n+1;i++) for(j=0;j<m;j++) printf("%d %d %d\n",i,j,f[i][j]);
	for(i=min(m-1,n);i;i--)
		ans=min(ans,f[(n+1)%mod][i]);
	printf("%d\n",ans);
	return 0;
}