目录
显示
题目链接
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; }