选数

选数

---

题目描述

n个数排成一排，从中选出k个数，使得和最大。要求相邻的两个数中最多选一个

输入输出格式

输入

共两行，第一行为n，k
第二行共有n个数，即题意中的数列

输出

仅一个数字，表示最大的和。

样例输入输出

输入：

5 2
5 2 1 -1 6

输出

11

数据范围

40%满足 \(n<=20,k<=3\)

60%满足 \(n<=800,k<=10\)

100%满足 \(n<=2000,k<=100\)

---

设dp数组为[i][j][k]

表示前i个数选j个且第i个数选与不选（k=1为选，k=0为不选）的最优解

dp[i][j][1]=dp[i-1][j-1][0]+a[i]

若第i个数选的话，那么就是前i-1的数，第i-1个数不选，已经选了j-1的数的最优值加上本身的值。

dp[i][j][0]=max(dp[i-1][j][1],dp[i-1][j][0])

若第i个数不选，则从前i-1的数，第i-1个数选或不选，已经选了j-1的数两种状态下的最优值转移过来。（要注意当前最优有可能不是全局最优，所以要从两种状态中转移过来）

---

#include<iostream> 
using namespace std;
int dp[2010][101][2];
int a[2010];
int main()
{
    cin.sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    dp[1][1][1]=a[1];
    dp[1][0][0]=0;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=k;j++)//从1开始，防止下标越界。而且选0个数的值全都是0，不用转移
        {
            dp[i][j][1]=dp[i-1][j-1][0]+a[i];
            dp[i][j][0]=max(dp[i-1][j][1],dp[i-1][j][0]);
        }
    printf("%d",max(dp[n][k][1],dp[n][k][0]));
}