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

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

Time Limit: 10 Sec  Memory Limit: 64 MB

Submit: 414  Solved: 199

[Submit][Status][Discuss]

Description

尽管奶牛们天生谨慎,她们仍然在住房抵押信贷市场中受到打击,现在她们开始着手于股市。 Bessie很有先见之明,她不仅知道今天S (2 <= S <= 50)只股票的价格,还知道接下来一共D(2 <= D <= 10)天的(包括今天)。 给定一个D天的股票价格矩阵(1 <= 价格 <= 1000)以及初始资金M(1 <= M <= 200,000),求一个最优买卖策略使得最大化总获利。每次必须购买股票价格的整数倍,同时你不需要花光所有的钱(甚至可以不花)。这里约定你的获利不可能超过500,000。 考虑这个牛市的例子(这是Bessie最喜欢的)。在这个例子中,有S=2只股票和D=3天。奶牛有10的钱来投资。 今天的价格 | 明天的价格 | | 后天的价格 股票 | | | 1 10 15 15 2 13 11 20   以如下策略可以获得最大利润,第一天买入第一只股票。第二天把它卖掉并且迅速买入第二只,此时还剩下4的钱。最后一天卖掉第二只股票,此时一共有4+20=24的钱。

Input

* 第一行: 三个空格隔开的整数:S, D, M

* 第2..S+1行: 行s+1包含了第s只股票第1..D天的价格

Output

* 第一行: 最后一天卖掉股票之后最多可能的钱数。

Sample Input

2 3 10 10 15 15 13 11 20

Sample Output

24

HINT

Source

Gold

题解:(我会说我一开始想到了DP?甚至想过BZOJ3359一样建图来求最短路呵呵)

其实还是DP。。。一个略有隐藏的背包,将前一天的价格视为价格,后面一天的视作价值(政治阴魂不散啊啊啊有木有),建立起一个完全背包问题,然后慢慢玩(本程序中b[i]表示当前一天钱还剩i时能创造的最大价值,然后递推下去)

 1 /**************************************************************
 2     Problem: 1578
 3     User: HtotBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:9176 ms
 7     Memory:4140 kb
 8 ****************************************************************/
 9  
10 var
11         i,j,k,l,n,m,tot:longint;
12         a:array[0..105,0..20] of longint;
13         b:Array[0..1000005] of longint;
14 function max(x,y:longint):longint;
15     begin
16         if x>y then max:=x else max:=y;
17     end;
18 begin
19         readln(n,m,l);
20         for i:=1 to n do
21                 for j:=1 to m do
22                         read(a[i,j]);
23         tot:=l;
24         for i:=2 to m do
25                 begin
26                         for j:=0 to tot do b[j]:=j;
27                         for j:=1 to n do
28                                 begin
29                                         if a[j,i]>a[j,i-1] then
30                                             for k:=a[j,i-1] to tot do b[k]:=max(b[k-a[j,i-1]]+a[j,i],b[k]);
31                                 end;
32                         tot:=b[tot];
33                 end;
34         writeln(tot);
35 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

1709: [Usaco2007 Oct]Super Paintball超级弹珠

1709: [Usaco2007 Oct]Super Paintball超级弹珠 Time Limit: 5 Sec  Memory Limit: 64 MB ...

36240
来自专栏HansBug's Lab

1593: [Usaco2008 Feb]Hotel 旅馆

1593: [Usaco2008 Feb]Hotel 旅馆 Time Limit: 10 Sec  Memory Limit: 64 MB Submit: 39...

32040
来自专栏HansBug's Lab

3433: [Usaco2014 Jan]Recording the Moolympics

3433: [Usaco2014 Jan]Recording the Moolympics Time Limit: 10 Sec  Memory Limit:...

28040
来自专栏HansBug's Lab

3298: [USACO 2011Open]cow checkers

3298: [USACO 2011Open]cow checkers Time Limit: 10 Sec  Memory Limit: 128 MB Subm...

28560
来自专栏CreateAMind

autoware 代码阅读 sensor

ROS driver to parse NMEA strings and publish standard ROS NavSat message types. ...

25120
来自专栏HansBug's Lab

3301: [USACO2011 Feb] Cow Line

3301: [USACO2011 Feb] Cow Line Time Limit: 10 Sec  Memory Limit: 128 MB Submit: ...

328100
来自专栏HansBug's Lab

1639: [Usaco2007 Mar]Monthly Expense 月度开支

1639: [Usaco2007 Mar]Monthly Expense 月度开支 Time Limit: 5 Sec  Memory Limit: 64 MB...

33060
来自专栏HansBug's Lab

1610: [Usaco2008 Feb]Line连线游戏

1610: [Usaco2008 Feb]Line连线游戏 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 13...

33460
来自专栏HansBug's Lab

1741: [Usaco2005 nov]Asteroids 穿越小行星群

1741: [Usaco2005 nov]Asteroids 穿越小行星群 Time Limit: 5 Sec  Memory Limit: 64 MB Sub...

27960
来自专栏HansBug's Lab

1668: [Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富

1668: [Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富 Time Limit: 3 Sec  Memory Limit: ...

34040

扫码关注云+社区

领取腾讯云代金券