fork download 
  1. 【题目大意】
  2. 一人预测了未来n天的股市行情，允许他有的最大股票数是Maxp，交易必须至少间隔W天，到第i天，他可以买进当天的股票，ap[i]一注，最多买as[i]注，可以在当天卖手里的股票，bp[i]一注，最多卖bs[i]注，问这样n天后他最多获利多少。
  3.  
  4. 【分析】
  5. dp做多点，方程还是很好想的，dp[i][j]: 到第i天有股票j拥有的最大获利，显然第i天要么什么都不做，要么买股票，要么卖股票，dp[i][j]由三个状态转移过来：
  6.  
  7. dp[i][j]= max{ dp[i-1][j];
  8.  
  9.                 dp[i-W-1][k] - ap[i] * (j-k); 
  10.  
  11.                 dp[i-W-1][k] + bp[i]* (k-j);
  12.  
  13.               }
  14.  
  15. 然后就是优化。 有这种要遍历第三维k的一般都要考虑是否能用到单调队列优化，关键是变形 t=dp[i-W-1][k]+ap[i]*k，这样t仅与k有关，而剩下的ap[i]*j仅与i，j有关是个定值，t在遍历j的时候就可以依次求出，且保存到一个单调递减队列，这样每次取队首元素就是最优结果了，时间复杂度很低。不想写太多了，网上翻了很多，我挑了个十分好的，贴下，代码最好自己能写。  我的代码风格是初始化head=0，rear=0，rear忘记-1了，查错许久。。。
  16.  
  17. 【代码】
  18. /*2011-07-07 16:21:23	Accepted 3401 281MS 16040K	2207 B	C++*/
  19. #define maxn 2005
  20. void up_max(int &x,int y){if(x<y)x=y;}
  21. int dp[maxn][maxn];
  22. int ap[maxn],bp[maxn],as[maxn],bs[maxn];
  23. int que[maxn],pos[maxn];
  24. int main()
  25. {
  26.     int T,n,maxp,W,i,j,k;
  27.     cin>>T;
  28.     while(T--)
  29.     {
  30.         cin>>n>>maxp>>W;
  31.         W++;
  32.         for(i=1;i<=n;i++)
  33.             scanf("%d%d%d%d",ap+i,bp+i,as+i,bs+i);
  34.         for(i=1;i<=n;i++)
  35.             for(j=0;j<=maxp;j++)
  36.                 dp[i][j]= -maxint;
  37.         //前W天要么无操作，要么只能买股票； 
  38.         for(i=1;i<=W;i++)
  39.             for(j=0;j<=as[i];j++)
  40.                 dp[i][j]= -ap[i]*j; //负号啊！！！ 
  41.  
  42.         for(i=2;i<=n;i++){
  43.             //第i天什么都不做； 
  44.             for(j=0;j<=maxp;j++)
  45.                 up_max(dp[i][j],dp[i-1][j]);
  46.  
  47.             if(i<=W) continue; //前W天的也必须更新； 
  48.             //第i天买股票；
  49.             int head=0,rear=0;
  50.             for(j=0;j<=maxp;j++){
  51.                 int t= dp[i-W][j]+ap[i]*j;
  52.                 while(head<rear&&t>que[rear-1]) 
  53.                     rear--;
  54.                 que[rear]= t;
  55.                 pos[rear++]= j;
  56.                 while(head<rear&&j-pos[head]>as[i])
  57.                     head++;
  58.                 up_max(dp[i][j],que[head]-ap[i]*j);
  59.             }
  60.             //第i天卖股票, 逆序做dp；
  61.             head=0, rear=0; 
  62.             for(j=maxp;j>=0;j--){
  63.                 int t= dp[i-W][j]+bp[i]*j;
  64.                 while(head<rear&&t>que[rear-1]) 
  65.                     rear--;
  66.                 que[rear]= t;
  67.                 pos[rear++]= j;
  68.                 while(head<rear&&pos[head]-j>bs[i]) 
  69.                     head++;
  70.                 up_max(dp[i][j],que[head]-bp[i]*j);
  71.             }
  72.         }
  73.         printf("%d\n",*max_element(dp[n],dp[n]+maxp+1));
  74.     }
  75. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/hyQJ3
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!