有点难
1142ms,82908KB

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+5;
int n,k,a[N];
int dp[N][105][2];
int main(){
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    memset(dp,-0x3f,sizeof(dp));
    dp[0][0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            dp[i][j][0]=dp[i-1][j][0];
            if(j) dp[i][j][0]=max(dp[i][j][0],dp[i-1][j-1][1]+a[i]);
            dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j][0]-a[i]);
        }
    }
    int ans=0;
    for(int i=0;i<=k;i++) ans=max(ans,dp[n][i][0]);
    printf("%d",ans);
    return 0;
}

空间优化（算是一种通法，模仿Deepseek的写法）
786ms,1116KB优化效果还是很显著的

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+5;
int n,k,a[N];
int dp[2][105][2];
int main(){
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    memset(dp,-0x3f,sizeof(dp));
    int now=0,prev=1;
    dp[prev][0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            dp[now][j][0]=dp[prev][j][0];
            if(j) dp[now][j][0]=max(dp[now][j][0],dp[prev][j-1][1]+a[i]);
            dp[now][j][1]=max(dp[prev][j][1],dp[prev][j][0]-a[i]);
        }
        swap(now,prev);
    }
    int ans=0;
    for(int i=0;i<=k;i++) ans=max(ans,dp[prev][i][0]);
    printf("%d",ans);
    return 0;
}