题解：SP19382 STK - Stock

一道动态规划题。

先分析状态。

• \(dp_{i\operatorname{and}1,k}\)：表示在第 \(i\) 天最多进行 \(k\) 次交易的最大利润。
• \(s_{i\operatorname{and}1,k}\)：表示在第 \(i\) 天之前的某天卖出之后，最多进行 \(k-1\) 次交易的最大利润减去当天的价格。

接下来分析转移方程

• 当 \(i=0\) 时，表示在第 \(0\) 天，没有进行任何交易，所以利润为 \(0\)，\(s\) 初始化为 INT_MIN，表示不可能的状态。
• 当 \(k=0\) 时，表示没有进行任何交易，所以利润为 \(0\),\(s\) 初始化为 INT_MIN。
• 其他情况下，通过以下状态转移公式：
  1. \(s_{i\operatorname{and}1,k} = \max(dp_{(i-1)\operatorname{and}1,k-1} - price_{i-1}, s_{(i-1)\operatorname{and}1,k}\)：表示在第 \(i\) 天最多进行 \(k\) 次交易的最大利润，这个最大利润要么来自于前一天最多进行 \(k-1\) 次交易并且在第 \(i-1\) 天买入，要么来自于前一天的同一状态。
  2. \(dp_{i\operatorname{and}1,k} = \max(dp_{(i-1)\operatorname{and}1,k}, s_{i\operatorname{and}1,k} + price_i)\)：表示在第 \(i\) 天卖出时的最大利润，要么不交易维持前一天的最大利润，要么在第 \(i\) 天卖出并且之前有一次有效的交易。

代码:

#include<bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int t,n,p;
	cin>>p;
	long long price[3003];
	while(p--) {
		cin>>n>>t;
		for(int i=0; i<n; i++)
			cin>>price[i];
		long long dp[2][t+1];
		long long s[2][t+1];
		for(int i=0; i<n; i++) {
			for(int k=0; k<=t; k++) {
				if(i==0)
					dp[0][k]=0,s[0][k]=INT_MIN;
				else if(k==0)
					dp[i&1][0]=0,s[i&1][0]=INT_MIN;
				else {
					s[i&1][k]=max(dp[(i-1)&1][k-1]-price[i-1],s[(i-1)&1][k]);
					dp[i&1][k]=max(dp[(i-1)&1][k],s[i&1][k]+price[i]);
				}
			}

		}
		cout<<dp[(n-1)&1][t]<<'\n';
	}
	return 0;
}