C.md

山大华特卧龙学校第一届ACM题目C

时间限制：1s 内存限制：128M

题目背景

苟利国家生死以，岂因祸福避趋之。——林则徐

标题

题目描述

公元前221年，秦始皇灭六国，统一了中原。

为了抵御北方少数民族的入侵，他下令修筑长城。

长城的修筑包含 $n$n个关键部位，从左到右编号为 $1$1- $n$n。如果这些部位没有防卫，那么就无法抵御匈奴。

为了抵御匈奴，秦始皇下令，这些部位要么建烽火台，要么建箭楼。

然而，修筑防御工事是需要人力物力财力的。如果第 $i$i个位置要建烽火台，那么会花费 $c_i$ci​的代价，如果第 $i$i个位置要建箭楼，设 $j$j表示它右面第一个烽火台的位置，那么花费的代价就是 $j-i$j−i，因为箭需要从烽火台运过来。同时，两个烽火台之间的距离不能大于 $k$k，否则箭矢的运输会受到影响。显然第 $n$n个位置一定要建烽火台。

现在秦始皇将长城的建造图纸给了你，要求你求出一个最优的修筑方案，使得总代价最小。

“苟利国家生死以，岂因祸福避趋之。保证完成任务！”

###输入输出格式

####输入格式

第一行两个正整数 $n,k$n,k，表示有 $n$n个关键部位，两个烽火台之间的距离不能大于 $k$k。

接下来一行 $n$n个正整数，第 $i$i个正整数 $c_i$ci​表示在第 $i$i个位置建设烽火台的代价。

输出格式
一个正整数，表示最小总代价。

###输入输出样例

####输入样例

5 2 5 3 4 2 5 

####输出样例

12 

####样例解释

在2,4,5三个位置建烽火台，其余的建箭楼，总花费为1+3+1+2+5=12。

###数据范围

$1\le k\le n\le 2000,1\le c_i\le 10^9$1≤k≤n≤2000,1≤ci​≤109

这道题不是我做的，然而我们也没做出来

但是赛后我打了一份代码

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <cmath>
#define int long long
#define maxn 3000
using namespace std ;
int n , k , c[maxn] , f[maxn] ;
int read() {//赛后比较有闲情逸致,想打快读了...
	int x = 0 ;
	int f = 1 ; char s = getchar() ;
	while(s>'9'||s<'0') {if(s=='-')f=-1;s=getchar();}
	while(s<='9'&&s>='0'){x=x*10+(s-'0');s=getchar();}
	return x*f ;
}
int m ;
int minn ;
signed main() {
	n = read() , k = read() ;
	for(int i = 1 ; i <= n ; i ++ ) {
		c[i] = read() ;
	}
	for(int i = 1 ; i <= n ;i ++) {
		int minn=100000000000000000;//这里一定开大..我开了1e7结果WA了一半QAQ
		for(int j=max(0ll,i-k);j<i;j++)
		  minn=min(minn,f[j]+(i-j)*i-i*(i+1)/2+j*(j+1)/2);
		f[i]=minn+c[i];
	}
	printf("%lld\n",f[n]) ;
}

泥萌的md有毒!
完结!