[洛谷 2938][USACO09FEB]Stock Market

题目链接

https://www.luogu.org/problem/P2938

题解

因为股票可以在同一天卖出再买入(且价格相同),我们的目标实际上是让每一天的收益最大。

所以这个问题就转化为了一个完全背包问题。

有一个小小的优化:如果当天股票价格高于第二天,就不用考虑了。

但时限还是很紧…不吸氧真的过不去…

(UPD 2019/08/23:向管理员反馈后时限增加到了 2s,不吸氧最慢的点跑到了 1.5 s…)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[55][15],f[500005];
int main()
{
 int s,d,m;
 scanf("%d%d%d",&s,&d,&m);
 for(int i=1;i<=s;i++)
  for(int j=1;j<=d;j++)
   scanf("%d",&a[i][j]);
 for(int i=1;i<d;i++)
 {
  int maxv=0,rem=m;
  memset(f,0,sizeof(f));
  for(int j=1;j<=s;j++)
   if(a[j][i+1]>a[j][i])
    for(int k=a[j][i];k<=m;k++)
    {
     f[k]=max(f[k],f[k-a[j][i]]+a[j][i+1]);
     if(f[k]+m-k>=maxv+rem)maxv=f[k],rem=m-k;
    }
  m=maxv+rem;
 }
 printf("%d\n",m);
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注