【luogu P2938股票市场】题解

股票市场

题目描述

尽管奶牛天生谨慎，它们仍然在住房抵押信贷市场中大受打击，现在它们准备在股市上碰碰运气。贝西有内部消息，她知道

假设在一开始，她筹集了

假设贝西有 10 元本金，股票价格如下：

股票	今天的价格	明天的价格	后天的价格
	10	15	15
	13	11	20

最赚钱的做法是：今天买入

输入格式

第一行：三个整数 S， D 和 M，

第二行到第 S + 1 行：第 i + 1 行有 D 个整数：

输出格式

单个整数：表示奶牛可以获得的最大钱数，保证这个数不会超过

输入输出样例

输入 #1

2 3 10 
10 15 15 
13 11 20

输出 #1

24 

题目有以下特殊性质，应当好好利用。
1. 每次交易的股票数量不限
2. 一种股票可以连续持有的数量不限。
3. 最终的答案比较小。

此外，我们在看看每天对于每种股票有哪些操作。
1. 买
2. 卖
3. 买了再卖

好，我们现在开始分析问题，如果只有一种股票，若何考虑？
显然，(在股价连续上升的情况下)肯定选择第一天买，最后一天卖出。

假如说第一天为第 i 天，最后一天为第 k 天。
考虑一下下面一种情况，你或许会有所启发。

假如到了k-1天，你发现如果这一天，你把你的股票卖了，你会赚到钱。
你首先最大化了当天的收益。
于是你选择把股票卖了，但是你拥有预知未来的能力，你发现，如果你再把股票买回来，放到第k天卖，你会有额外的收益。
于是你为了第k天钱更多，又把你的收益拿来买股票，换取第k天最大化收益。

也就是说，当第k天时，用第k-1天最大化的收益买股票(或者不买)，可以得到第k天的最大化收益。

也许你早就看出来了，这道题的本质是一个背包，因为数量无限，所以是个完全背包。
再看看题目告诉我们的，最终的答案，也就是最大化收益比较小，那就可以把前一天最大化收益做成背包的上限。
最大化当前的收益。
最后可以套完全背包的模板了 ~打板子使我快乐~

#include<iostream>
#include<cstdio>
#include<cstring>
#define R register int
#define max(x,y) (x>y?x:y)
using namespace std;
int s,d,m,ma;
int a[20][100],f[550000];
inline void read(int &x){
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}
int main()
{
    read(s),read(d),read(m);
    for(R i=1;i<=s;i++)
        for(R j=1;j<=d;j++) 
            read(a[j][i]);
    for(R k=2;k<=d;k++){
        memset(f,0,sizeof(f));
        ma=0;
        for(R i=1;i<=s;i++)//此时m为前一天的最大化收益
            for(R j=a[k-1][i];j<=m;j++){//完全背包和01背包，仅仅在循环的顺序上有所差异
                f[j]=max(f[j],f[j-a[k-1][i]]+a[k][i]-a[k-1][i]);//因为前一天有钱，可以买，放到这一天来卖。差价为增加的收益。
                ma=max(ma,f[j]);//最大化收益    
            }
        m+=ma;//这是m为当天的最大化收益
    }
    printf("%d",m);
}