题解当打卡…

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<cstring>
#include<bitset> 
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define PI  acos(-1)
//CLOCKS_PER_SEC clock()函数每秒执行次数
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 3e5+5,M = N * 2;
int mod = 1e9 +7;
int n,m,k,S,T;
int w[N],f[2][N][2]; 
void solve(){
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i) cin >> w[i];
    //第N个小时没有睡觉，则第一个小时睡觉与不睡觉收益都为0
    memset(f,0xcf,sizeof(f));
    f[1][0][0] = f[1][1][1] = 0; 
    for(int i = 2 ; i <= n ; ++i){
        for(int j = 0 ; j <= m ; ++j){
            f[i & 1][j][0] = max(f[i - 1 & 1][j][0],f[i - 1 & 1][j][1]);
            if(j) f[i & 1][j][1] = max(f[i - 1 & 1][j - 1][0],f[i - 1 & 1][j - 1][1] + w[i]);
        }
    }
    int ans = f[n & 1][m][0];
    //第N个小时在睡觉，则第一个小时睡觉收益都为w[1]; 
    memset(f,0xcf,sizeof(f));
    f[1][0][0] = 0,f[1][1][1] = w[1]; 
    for(int i = 2 ; i <= n ; ++i){
        for(int j = 0 ; j <= m ; ++j){
            f[i & 1][j][0] = max(f[i - 1 & 1][j][0],f[i - 1 & 1][j][1]);
            if(j) f[i & 1][j][1] = max(f[i - 1 & 1][j - 1][0],f[i - 1 & 1][j - 1][1] + w[i]);
        }
    }
    ans = max(ans,f[n & 1][m][1]);
    cout << ans << endl;
}

signed main(){
    IOS;
    solve();
    return 0;
}
/*
*
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/