欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

选数

程序员文章站 2022-03-14 20:06:44
...

选数


题目描述

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]));
}