[洛谷 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;
}