视频题解
时间轴
大盗阿福 0:00
股票买卖 IV 2:15
股票买卖 V 4:55
设计密码 7:25
AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve(){
int n,m; cin >> n >> m;
vector<int> a(n + 1); for(int i = 1; i <= n; i ++) cin >> a[i];
vector<vector<int>> dp(m + 1, vector<int>(2, -2e18));
dp[0][0] = 0;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
dp[j][0] = max(dp[j][0], dp[j][1] + a[i]);
dp[j][1] = max(dp[j][1], dp[j - 1][0] - a[i]);
}
}
int res = 0;
for(auto i:dp) res = max(res, i[0]);
cout << res;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
while(T --){
solve();
}
}