ACMer想去见自己的好朋友。已知在路上一共有n个结点，每个结点都有一定的权值。要求ACMer必须经过n个结点中的k个(不能多也不能少)。且经过的这k个结点两两不能相邻。求经过k个结点权值和的最小值。
1581: 漂洋过海来看你
时间限制: 1 Sec 内存限制: 128 MB提交: 1 解决: 1
[提交][状态][讨论版][命题人:]
题目描述
输入描述
每组输入数据有两行,第一行有两个数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个数的和要求最小。
来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版