题目描述

blablabla

样例

blablabla

算法

这题难点在于处理只能用一次的环,分2次dp就好,第一次是是1那里没环,第二次是有环,直接取w[1],然后进行转移即可.滚动数组直接%2就完事…转移方程就很简单了,具体有注释.

(线性dp) $O(nb)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=3832;
const int inf=0x3f3f3f3f;
int f[2][N][2];
int w[N];
//到了第i个位子 睡了几h 这个点睡了吗?
int main()
{
    int n,b;
    scanf("%d%d",&n,&b);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
    }
    memset(f,-0x3f,sizeof f);
    f[1][0][0]=0,f[1][1][1]=0;
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=min(b,i);j++)
        {
            f[i%2][j][0]=-inf;
            f[i%2][j][1]=-inf;
            f[i%2][j][0]=max(f[(i-1)%2][j][1],f[(i-1)%2][j][0]);
            if(j) f[i%2][j][1]=max(f[(i-1)%2][j-1][1]+w[i],f[(i-1)%2][j-1][0]);
        }
    }
    //dp到n了.
    int ans=max(f[n%2][b][1],f[n%2][b][0]);
    memset(f,-0x3f,sizeof f);
    f[1][1][1]=w[1];
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=min(b,i);j++)
        {
            f[i%2][j][0]=-inf;
            f[i%2][j][1]=-inf;
            f[i%2][j][0]=max(f[(i-1)%2][j][1],f[(i-1)%2][j][0]);
            if(j) f[i%2][j][1]=max(f[(i-1)%2][j-1][1]+w[i],f[(i-1)%2][j-1][0]);
        }
    }
    ans=max(ans,f[n%2][b][1]);
    cout<<ans<<endl;
    return 0;
}