bzoj1578[Usaco2009 Feb]Stock Market 股票市场*

bzoj1578[Usaco2009 Feb]Stock Market 股票市场

题意：

知道S只股票D天的价格。初始时有M元，问最后最多多少钱。S≤50，D≤10，M≤200000。

题解：

首先可以得出头日买了股票第二天立刻卖掉等价与拖几天再卖（因为可以卖掉后立刻买相同的数量）。故对每一天单独做完全背包，得到每天的最大收益第二天用即可。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define INF 0x3fffffff
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 using namespace std;
 7 
 8 inline int read(){
 9     char ch=getchar(); int f=1,x=0;
10     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
11     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
12     return f*x;
13 }
14 int a[60][20],s,d,m,f[500010],mx;
15 int main(){
16     s=read(); d=read(); m=read(); inc(i,1,s)inc(j,1,d)a[i][j]=read(); mx=m;
17     inc(i,1,d-1){
18         memset(f,0,sizeof(f));
19         inc(j,1,s)inc(k,a[j][i],mx){f[k]=max(f[k],f[k-a[j][i]]+a[j][i+1]-a[j][i]);} mx=mx+f[mx];
20     }
21     printf("%d",mx); return 0;
22 }

20161011