选择

 

 

 

 题解：

 

其实画一画很容易知道：偶数个的话，最多选\(\left \lfloor \frac{i}{2}\right \rfloor\)；奇数个的话，可以选\(\left \lfloor \frac{i}{2}\right \rfloor\)个也可以选\(\left \lfloor \frac{i}{2}\right \rfloor+1\)个

我们就设dp[i][0]表示前i个选了\(\left \lfloor \frac{i}{2}\right \rfloor\)个，dp[i][1]表示前i个选了\(\left \lfloor \frac{i}{2}\right \rfloor+1\)

AC_Code:

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long ll;
 4 #define endl '\n'
 5 const int maxn = 2e5+10;
 6 const ll inf=1e15;
 7 
 8 ll a[maxn],dp[maxn][2];
 9 int n,x;
10 
11 int main()
12 {
13     cin>>n>>x;
14     for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
15     a[x]+=inf;
16 
17     dp[1][1]=a[1];
18     for(int i=2;i<=n;i++){
19         if( i%2==0 ){
20             dp[i][0]=max(dp[i-1][1],dp[i-2][0]+a[i]);
21         }else{
22             dp[i][0]=max(dp[i-1][0],dp[i-2][0]+a[i]);
23             dp[i][1]=dp[i-2][1]+a[i];
24         }
25     }
26     cout<<dp[n][0]-inf<<endl;
27     return 0;
28 }