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\).
Don't buy or sell, waste your time
\(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))\)
Stock trading 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;
}
The result is only \ (\ color{red}\textbf{10 points} \).
Stock trading v2 0
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} \)