Responsive image

问题 1581 --漂洋过海来看你

1581: 漂洋过海来看你

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

ACMer想去见自己的好朋友。已知在路上一共有n个结点，每个结点都有一定的权值。要求ACMer必须经过n个结点中的k个(不能多也不能少)。且经过的这k个结点两两不能相邻。求经过k个结点权值和的最小值。

输入描述

每组输入数据有两行,第一行有两个数n,k(1<<=n<2000，0<k<=(n+1)/2).第二行有n个整数分别表示每个结点的权值(权值是一个小于10^9的正整数).

输出描述

每组数据输出所选k个节点和的最小值。

样例输入

2 1
1 3
3 2
1 2 3
4 2
4 1 1 1

样例输出

1
4
2

提示

友情提示：n个数选择k个互不相邻的数且这k个数的和要求最小。

来源

hdu 

[提交][状态]
ACM算法攻关部