選數

---

題目描述

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

轉載于:https://www.cnblogs.com/Lance1ot/p/8495933.html

總結

以上是生活随笔為你收集整理的选数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。