BZOJ 1578: [Usaco2009 Feb]Stock Market 股票市场

题目地址

描述

尽管奶牛们天生谨慎,她们仍然在住房抵押信贷市场中受到打击,现在她们开始着手于股市。 Bessie很有先见之明,她不仅知道今天$S (2 \leq S \leq 50)$只股票的价格,还知道接下来一共$D(2 \leq D \leq 10)$天的(包括今天)。
给定一个$D$天的股票价格矩阵$(1 \leq 价格 \leq 1000)$以及初始资金$M(1 \leq M \leq 200,000)$,求一个最优买卖策略使得最大化总获利。
每次必须购买股票价格的整数倍,同时你不需要花光所有的钱(甚至可以不花)。
这里约定你的获利不可能超过$500,000$。

分析

是一道想法还是挺妙的一道题目
看这道题目的时候总觉得有一点熟悉的感觉,怎么这么像背包DP,事实上这就是一个背包DP QAQ

但是还是有一个挺奇妙的想法就是“不用考虑一支买进的股票在哪一天卖出,我们只需要今天买进明天卖出就可以了”

有了这个结论那么就好做了,我们把每一天当做一个完全背包来做,背包的体积为手中持有的资金,背包有两个状态:

  1. 一个是不买进,也不卖出
  2. 还有一个是买进当前的一只股票,并在明天卖出

那么我们有状态$dp[k]$为手中持有资金为$k$时能获利最多的钱
转移方程为

每天做一次完全背包并更新手中持有资金,然后做出来了QAQ

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//  BZOJ 1578 [Usaco2009 Feb]Stock Market 股票市场
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved;
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_S = 50 + 3;
const int MAX_D = 10 + 3;
const int MAX_M = 500000 + 3;
const int INF = 0x3f3f3f3f;
int s, d, m;
int w[MAX_S][MAX_D];
int dp[MAX_M], ans;

int main()
{
s = readIn(), d = readIn(), m = readIn();
for (int i = 0; i < s; ++i) {
for (int j = 0; j < d; ++j) w[i][j] = readIn();
}

ans = m;
memset(dp, 0, sizeof dp);
for (int i = 0; i < d; ++i) {
memset(dp, 0, sizeof dp);
for (int j = 0; j < s; ++j) {
for (int k = w[j][i]; k <= ans; ++k) {
dp[k] = max(dp[k], dp[k - w[j][i]] + w[j][i + 1] - w[j][i]);
}
}
ans += dp[ans];
}
printf("%d\n", ans);
return 0;
}
Partager