股票市场Stock Market

标签： 动态规划 背包DP

---

题目描述

尽管奶牛天生谨慎，它们仍然在住房抵押信贷市场中大受打击，现在它们准备在股市上碰碰运气。贝西有内部消息，她知道S只股票在今后D天内的价格。
假设在一开始，她筹集了M元钱，那么她该怎样操作才能赚到最多的钱呢？贝西在每天可以买卖多只股票，也可以多次买卖同一只股票，交易单位必须是整数，数量不限。举一个牛市的例子：
假设贝西有 10 元本金，股票价格如下：
股票 今天的价格 明天的价格 后天的价格
A 10 15 15
B 13 11 20

最赚钱的做法是：今天买入 A股 1 张，到明天把它卖掉并且买入 B 股 1 张，在后天卖掉 B股，这样贝西就有 24 元了。

输入格式

第一行：三个整数 S，D 和 M，$2≤S≤50 ; 2≤D≤10 ; 1≤M≤200000 $
第二行到第 S + 1 行：第 i + 1 行有 D 个整数： Pi;1到 Pi;D表示第 i种股票在第一天到最后一天的售价，对所有 $1 ≤ j ≤ D,1≤Pi;j≤1000$

输出格式

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

输入输出样例

输入样例#1：
2 3 10
10 15 15
13 11 20
输出样例#1：
24

题解

一个很简单的思想便是在i天时，枚举1到i-1天，然后枚举股票种类数，枚举持钱数分别转移，但这样转移肯定会超时。分析题目性质，如果我们从第一天买入A股，第三天卖出，完全等价于第一天买入A股，第二天卖出A股，第二天买入A股，第三天卖出A股。（感觉很像放屁…）
我们这样思考的话就可以发现，每天的利润只和前一天有关，因此我们只用顺序枚举天数即可挨个转移了，而且题目还有限制：保证奶牛最多不会超过500000的钱，这相当于就是在暗示我们状态设计了（然鹅我太弱并没有开出来…）
设F[i][j]表示在i天持有j钱所获得的最大利润，这里j就相当于容量，利润就相当于价值，并且股票可以无限买，所以就转换成完全背包问题了，每次所获得利润加上本钱就构成了下一天的本钱（容量）
由于只和状态前一天有关，所以可以滚动为一维

代码

#include<bits/stdc++.h> 
#define N 55
#define M 500010
using namespace std;

void read(int &ans)
{
    ans = 0; int f = 1;
    char x = getchar();
    while(x > '9' || x < '0') {if(x == '-') f = -1; x = getchar();}
    while(x >= '0' && x <= '9') ans = ans * 10 + x - '0', x = getchar();
    ans *= f;
}

int main()
{
    int s, d, m, tmp;
    int a[N][N], f[M];
    scanf("%d%d%d", &s, &d, &m);
    for(register int i = 1; i <= s; i ++)
        for(register int j = 1; j <= d; j ++)
            scanf("%d", &a[j][i]);
    tmp = m;
    for(register int i = 2; i <= d; i ++)
    {
        memset(f, 0, sizeof(f));
        for(register int j = 1; j <= s; j ++)
        {
            for(register int k = a[i - 1][j]; k <= tmp; k ++)
                if(f[k] < f[k - a[i - 1][j]] + a[i][j] - a[i - 1][j])
                   f[k] = f[k - a[i - 1][j]] + a[i][j] - a[i - 1][j];
        }
        tmp = f[tmp] + tmp; 
    }        
    printf("%d", tmp);    
    return 0;
}

心得

感觉对题目划分阶段很重要啊，并且要注意题目的特殊限制或者条件，往往这就是突破口。