## Problem surface

Recently \ (\ text{lxhgww} \) became addicted to investing in stocks. After a period of observation and study, he summarized some rules of stock market.

Through observation for a period of time, \ (\ text{lxhgww} \) predicted the trend of a stock in the next \ (T \) days. The buying price of the stock on the \ (I \) day was \ (AP_i \), and the selling price of the stock on the \ (I \) day was \ (BP_i \) (the data guarantees that there are \ (AP_i \geq BP_i \) for each \ (I \), but it cannot be traded without restrictions every day, Therefore, the stock exchange stipulates that one purchase on the \ (I \) day can only buy \ (AS_i \) shares at most, and one sale can only sell \ (BS_i \) shares at most.

In addition, the stock exchange has also formulated two regulations. In order to avoid crazy trading, the stock exchange stipulates that there should be at least \ (w \) days between two transactions (both buying and selling on a certain day are considered as one transaction), that is, if a transaction occurs on \ (i \), no transaction can occur from \ (i+1 \) to \ (i+W \). At the same time, in order to avoid monopoly, the stock exchange also stipulates that the number of shares in a person's hand cannot exceed \ (\ text{MaxP} \) at any time.

Before the \ (1 \) day, \ (\ text{lxhgww} \) has a lot of money (it can be considered that the amount of money is unlimited), but there is no stock. Of course, \ (\ text{lxhgww} \) wants to make the most money after \ (T \) day. Smart programmers, can you help him?

## Case by case discussion

I used to be interested in economics, so I can still understand the relationship.

### Preparation stage

The Lord can activate skills

Assign all States to \ (- inf \), which can be used

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

In this article, \ (f[i][j] \) refers to the amount of money made by holding \ (j \) shares on the \ (I \) day.

### Empty handed white wolf, buy out of thin air

When you don't have money, buy it directly.

$$f[i][j]=-AP_i \times j$$.

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

### The bull market is coming. Buy

First of all, the interval between each transaction is at least \ (W \) days, so the last transaction is at least \ (i-W-1 \) days.

And \ (\ because \) state transition equation \ (f[i][j] = max \ {f [I-1] [J], f[i][j] \} \) moves the optimal solution to \ (f[i][j] \) larger \ (f[i][j] \), so \ (f[i-W-1] \) must be optimal.

Own \ (k \) shares in \ (i-W-1 \) days.

Then \ (j \gt k \), you can only buy positive integer (\ (Z ^ + \)) shares!

Purchased \ ((j-k) \) shares and spent \ ((j-k)\times AP_i\).

You can't buy too many stocks at a time. You can only buy \ (AS_i \), so) \ ((j-AS_i) \le k \lt j \)

Finishing, get $f [i] [J] = max {f [i] [J], f [i-w-1] [k] - (J-K) \ times ap_i} \ (& nbsp; & nbsp; & nbsp; \) ((j-as_i) \ Le K \ LT J)$

### The bear market is coming. Sell it

Write the state transition equation directly:

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

#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;
}

The result is only \ (\ color{red}\textbf{10 points} \).

It is found that i may be less than or equal to w, and the coordinates are directly negative.

Resolution code:

if(i<=w){
continue;
}

Final code:

#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}$$ points.

## Sliding window optimization | stock trading 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 points}$$

Keywords: OI

Added by sotusotusotu on Wed, 26 Jan 2022 11:21:16 +0200