题目描述 Description
给出一个长度为N的序列A(A1,A2,A3,...,AN)。现选择K个互不相同的元素，要求： 1.两两元素互不相邻
2.元素值之和最大
输入描述 Input Description
第一行两个正整数N，K。 接下来一行N个整数，描述A。
输出描述 Output Description
输出一行一个整数，描述答案（最大和）。
样例输入 Sample Input
样例1：
7 3
3 5 7 -1 9 10 7
样例2：
7 3
3 21 7 -1 9 20 7
样例输出 Sample Output
样例1：
23
样例2：
40
数据范围及提示 Data Size & Hint
测试点编号 数据范围
1,2,3 K≤N≤20
4,5,6,7,8,9,10 K≤N≤1000
/*
比较水的DP
f[i][j][0/1]表示前i个数里取k个并且第i个取或不取的最大值,转移方程就比
较好想了，另外可以用滚动数组优化空间，鄙人比较懒，所以……
*/
#include<cstdio>
#include<iostream>
#define ll long long
#define M 1010
using namespace std;
ll f[M][M][],a[M];int n,k;
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
cin>>a[i];
for(int i=;i<=n;i++)
for(int j=;j<=min(k,(i+)/);j++)//注意这里循环到 min(k,(i+1)/2)
{
f[i][j][]=max(f[i-][j][],f[i-][j][]);
if(j)f[i][j][]=f[i-][j-][]+a[i];
}
cout<<max(f[n][k][],f[n][k][]);
return ;
}