SP283 NAPTIME-Naptime

一个环上有n个点，价值 a[i]，现在要选择m个点，

其中连续段的第一个元素的价值不算，求总和最大？

先考虑一条链

f[i][j][0/1] ,j 是目前选择了的点的个数， 0/1 当前点i 是否选择

状态转移：

  f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1])
  f[i][j][1]=max(f[i-1][j-1][0],f[i-1][j-1][1]+a[i])

现在考虑环的问题

环上的dp要注意可能出现 [n-1,3] 这种情况 ，其中的3是下一轮的3

 所以直接开两倍的点 ，像        石子合并 这题

但这题观察方程发现只有 n 和 1 的位置要考虑

我们枚举 n 的状态，即 元素n是否选择

两种状态对应dp的边界设置

 // f[1][0][0]=f[1][1][1]=0  选择n,  那么 1 不算价值
 // f[1][0][0]=0, f[1][1][1]=a[1]  不选择，那么 1 算价值

#include <iostream>
#include <cstring>
using namespace std; 
 const int N=4000;
 
 int n,m,a[N],f[N][N][2];
 
 void solve(){
 	int i,j;
 	cin>>n>>m;
    for(i=1;i<=n;i++) cin>>a[i];
    
    int ans=-1e9;
    memset(f,-127,sizeof f);
    f[1][0][0]=f[1][1][1]=0;
    
   for(i=2;i<=n;i++)
    for(j=0;j<=m&&j<=i;j++){
      f[i][j][0] =max(f[i-1][j][0],f[i-1][j][1]);
	  f[i][j][1] =max(f[i-1][j-1][1]+a[i],f[i-1][j-1][0]);
    }
    ans=max(ans,f[n][m][0]);
    
    memset(f,-127,sizeof f);
    f[1][0][0]=0,f[1][1][1]=a[1];
    
   for(i=2;i<=n;i++)
    for(j=0;j<=m&&j<=i;j++){
      f[i][j][0] =max(f[i-1][j][0],f[i-1][j][1]);
	  f[i][j][1] =max(f[i-1][j-1][1]+a[i],f[i-1][j-1][0]);
    }
    ans=max(ans,f[n][m][1]);
    cout<<ans<<endl;
 }
 signed main(){ 
    int cas; cin>>cas;
    while(cas--) solve();
    
}