题面

最近 \(\text{lxhgww}\) 又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。

通过一段时间的观察，\(\text{lxhgww}\) 预测到了未来 \(T\) 天内某只股票的走势，第 \(i\) 天的股票买入价为每股 \(AP_i\)，第 \(i\) 天的股票卖出价为每股 \(BP_i\)（数据保证对于每个 \(i\)，都有 \(AP_i \geq BP_i\)），但是每天不能无限制地交易，于是股票交易所规定第 \(i\) 天的一次买入至多只能购买 \(AS_i\) 股，一次卖出至多只能卖出 \(BS_i\) 股。

另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔 \(W\) 天，也就是说如果在第 \(i\) 天发生了交易，那么从第 \(i+1\) 天到第 \(i+W\) 天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的股票数不能超过 \(\text{MaxP}\)。

在第 \(1\) 天之前，\(\text{lxhgww}\) 手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然，\(T\) 天以后，\(\text{lxhgww}\) 想要赚到最多的钱，聪明的程序员们，你们能帮助他吗？

分情况讨论

本人曾经对经济学比较感兴趣，所以关系还是能弄懂得。

准备阶段

主公可以发动技能

把所有状态赋值为\(-inf\)，可以使用

memset(f,0x80,sizeof(f));

在本文中，\(f[i][j]\)指在第\(i\)天持有\(j\)支股票的赚钱数。

空手套白狼，凭空购买

当你没有钱时，直接购买（还欠钱）。

\(f[i][j]=-AP_i \times j\)。

不买不卖，虚度光阴

\(f[i][j]=max \{ f[i-1][j],f[i][j]\}\)

牛市来了，买买买

首先，每次交易至少间隔\(W\)天，所以上一次交易至少在\(i-W-1\)天。

又\(\because\)状态转移方程\(f[i][j]=max \{ f[i-1][j],f[i][j]\}\)把最优解移到了\(i\)更大的\(f[i][j]\)，所以\(f[i-W-1]\)一定最优。

设在\(i-W-1\)天拥有\(k\)张股票。

那么\(j \gt k\)，购买股票只能购买正整数(\(Z^+\))张嘛！

购买了\((j-k)\)张股票，花费\((j-k)\times AP_i\)。

股票一次不能买太多，只能买\(AS_i\)支，所以）\((j-AS_i) \le k \lt j\)

整理，得$f[i][j]=max { f[i][j], f[i-w-1][k]-(j-k) \times AP_i} \(   \)((j-AS_i) \le k \lt j)$

熊市来了，卖卖卖

直接写状态转移方程吧：

\(f[i][j]=max \{ f[i][j],f[i-w-1][k]+(k-j) \times BP_i \}\)   \((j \lt k \le(j+BS_i))\)

股票交易v1.0

#include<bits/stdc++.h>
using namespace std;

int t,m,w;
int f[2005][2005];
int ans=INT_MIN;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(f,0x80,sizeof(f)); // f->(-inf)[] 
	cin>>t>>m>>w;
	for(int i=1;i<=t;i++){
		int ap,bp,as,bs;
		cin>>ap>>bp>>as>>bs;
		for(int j=0;j<=as;j++){
			f[i][j]=-1*ap*j;
		}
		for(int j=0;j<=m;j++){
			f[i][j]=max(f[i][j],f[i-1][j]);
		}
		for(int j=0;j<=m;j++){
			for(int k=j-as;k>=0&&k<j;k++){
				f[i][j]=max(f[i][j],f[i-w-1][k]-(j-k)*ap);
			}
		}
		for(int j=m;j>=0;j--){
			for(int k=j+1;k<=j+bs;k++){
				f[i][j]=max(f[i][j],f[i-w-1][k]+(k-j)*bp);
			}
		}
	}
	for(int i = 0 ; i <= m ; i++)
        ans = max(ans , f[t][i]);
    printf("%d",ans);
	return 0;
}

结果只有\(\color{red}\textbf{10分}\)。

股票交易v2.0

发现i可能会小于或等于w，这时坐标直接为负数。

解决代码：

if(i<=w){
	continue;
}

最终代码：

#include<bits/stdc++.h>
using namespace std;

int t,m,w;
int f[2005][2005];
int ans=INT_MIN;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(f,0x80,sizeof(f)); // f->(-inf)[] 
	cin>>t>>m>>w;
	for(int i=1;i<=t;i++){
		int ap,bp,as,bs;
		cin>>ap>>bp>>as>>bs;
		for(int j=0;j<=as;j++){
			f[i][j]=-1*ap*j;
		}
		for(int j=0;j<=m;j++){
			f[i][j]=max(f[i][j],f[i-1][j]);
		}
		if(i<=w){
			continue;
		}
		for(int j=0;j<=m;j++){
			for(int k=j-as;k>=0&&k<j;k++){
				f[i][j]=max(f[i][j],f[i-w-1][k]-(j-k)*ap);
			}
		}
		for(int j=m;j>=0;j--){
			for(int k=j+1;k<=j+bs;k++){
				f[i][j]=max(f[i][j],f[i-w-1][k]+(k-j)*bp);
			}
		}
	}
	for(int i = 0 ; i <= m ; i++)
        ans = max(ans , f[t][i]);
    printf("%d",ans);
	return 0;
}

\(\color{orange}\textbf{60}\)分。

滑动窗口优化 | 股票交易v3.0

#include<bits/stdc++.h>
using namespace std;

int t,m,w;
int f[2005][2005],q[2005];
int ans=INT_MIN;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(f,0x80,sizeof(f)); // f->(-inf)[] 
	cin>>t>>m>>w;
	for(int i=1;i<=t;i++){
		int ap,bp,as,bs;
		cin>>ap>>bp>>as>>bs;
		for(int j=0;j<=as;j++){
			f[i][j]=-1*ap*j;
		}
		for(int j=0;j<=m;j++){
			f[i][j]=max(f[i][j],f[i-1][j]);
		}
		if(i<=w){
			continue;
		}
//		for(int j=0;j<=m;j++){
//			for(int k=j-as;k>=0&&k<j;k++){
//				f[i][j]=max(f[i][j],f[i-w-1][k]-(j-k)*ap);
//			}
//		}
//		for(int j=m;j>=0;j--){
//			for(int k=j+1;k<=j+bs;k++){
//				f[i][j]=max(f[i][j],f[i-w-1][k]+(k-j)*bp);
//			}
//		}
		int left=1,right=0;
		for(int j=0;j<=m;j++){
			while(left<=right&&q[left]<j-as){
				left++;
			}
			while(left<=right&&f[i-w-1][q[right]]+q[right]*ap<=f[i-w-1][j] + j * ap){
				right--;
			}
			q[++right]=j;
			if(left<=right){
				f[i][j]=max(f[i][j],f[i-w-1][q[left]]+q[left]*ap-j*ap);
			}
		}
		left=1,right=0;
		for(int j=m;j>=0;j--){
			while(left<=right&&q[left]>j+bs){
				left++;
			}
			while((left<=right)&&f[i-w-1][q[right]]+q[right]*bp<=f[i-w-1][j]+j*bp){
				right--;
			}
			q[++right]=j;
			if(left<=right){
				f[i][j]=max(f[i][j],f[i-w-1][q[left]]+q[left]*bp-j*bp);
			}
		}
	}
	for(int i = 0 ; i <= m ; i++){
		ans = max(ans , f[t][i]);
	}
    printf("%d",ans);
	return 0;
}

\(\color{green}\textbf{100分}\)