题目传送门

这是一个死dp！

我们怎么考虑呢？
不难发现，我们可以用\(dp_{i,j}\)表示前i个人选j个的最大收益，但是这是有后效性，也就是说会影响到\(i+n/2\)的位置的选择。座椅不好做

那么我们怎么解决呢，我们的难点在于i和i+n/2会互相影响。那么我们可以考虑把它们两个包在一起，问题就变成了前i对人选j个的最大收益是多少，这就简单死了！

转移方程如下

1.不选第i队\(dp_{i,j}=dp_{i-1,j}\)
2.选其中一个人\(dp_{i,j}=dp_{i-1,j}+max(a_i,a_{i+n/2)\)
3.两个都选\(dp_{i,j}=dp_{i-1,j}+b_i\)

注意，转移方程也要选最优的转移

代码如下

#include<bits/stdc++.h>
#include <cstdio>
using namespace std;

#define int long long

int a[5001],b[5001],c1[5001],c2[5001];
int n,k;
int dp[2501][5001];

signed main(){
    freopen("li.in","r",stdin);
    freopen("li.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    int len=0;
    for(int i=1;i<=n/2;i++) c1[++len]=i,c2[len]=i+n/2;
    memset(dp,128,sizeof dp);
    dp[0][0]=0;
    for(int i=1;i<=len;i++){
        for(int j=0;j<=k;j++){
            if(j<2){
                if(j<1) dp[i][j]=dp[i-1][j];
                else dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i-1][j-1]+max(a[c1[i]],a[c2[i]]) ) );
            }else{
                dp[i][j]=max(dp[i][j],max(dp[i-1][j],max(dp[i-1][j-1]+max(a[c1[i]],a[c2[i]]),dp[i-1][j-2]+b[c1[i]]+b[c2[i]]) )) ;
            }
        }
    }
    cout<<dp[len][k]<<endl;
}