题目描述 

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
        
         #include
         
          #define ll long long#define M 1010using namespace std;ll f[M][M][2],a[M];int n,k;int main(){    scanf("%d%d",&n,&k);    for(int i=1;i<=n;i++)      cin>>a[i];    for(int i=1;i<=n;i++)      for(int j=0;j<=min(k,(i+1)/2);j++)//注意这里循环到 min(k,(i+1)/2)      {          f[i][j][0]=max(f[i-1][j][1],f[i-1][j][0]);          if(j)f[i][j][1]=f[i-1][j-1][0]+a[i];      }    cout<