[文章目录]
Description
尽管奶牛们天生谨慎，她们仍然在住房抵押信贷市场中受到打击，现在她们开始着手于股市。 Bessie很有先见之明，她不仅知道今天S (2 <= S <= 50)只股票的价格，还知道接下来一共D(2 <= D <= 10)天的（包括今天）。 给定一个D天的股票价格矩阵（1 <= 价格 <= 1000）以及初始资金M(1 <= M <= 200,000)，求一个最优买卖策略使得最大化总获利。每次必须购买股票价格的整数倍，同时你不需要花光所有的钱（甚至可以不花）。这里约定你的获利不可能超过500,000。
一开始想到每两天的股票差价跑一遍背包。实际上第i天买入，第j天卖出相当于i天买入，i+1天卖出，i+1天再买入。。。
所以相邻2天跑一遍背包就好了。将i天的价格当做体积，i+1天的价格当做价值，不买的话就当做一个体积价格都为1的物品就好了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int s,d,map[20][60];
int f[701000],dp[20];
int main()
{
scanf("%d%d%d",&s,&d,&dp[1]);
for(int i=1;i<=s;++i)
for(int j=1;j<=d;++j)
scanf("%d",&map[j][i]);
for(int i=2;i<=d;++i)
{
memset(f,-0x3f,sizeof(int)*(dp[i-1]+10)); f[0]=0;
for(int j=1;j<=s;++j)
{
for(int k=map[i-1][j];k<=dp[i-1];++k)
f[k]=max(f[k],f[k-map[i-1][j]]+map[i][j]);
}
for(int k=1;k<=dp[i-1];++k)
f[k]=max(f[k],f[k-1]+1);
dp[i]=f[dp[i-1]];
}
printf("%d",dp[d]);
return 0;
}