USACO 2009 Feb 股票市场 Stock Market
Description
尽管奶牛们天生谨慎,她们仍然在住房抵押信贷市场中大受打击,现在她们准备在股市 上碰碰运气。贝西开挂了,她知道S只股票在今后D天内的价格。
假设她一开始有M元钱,怎么操作才能在D天后赚到最多的钱?股票在市场上的供应量 可以看成是无限的,但买卖股票必须以整数为最小交易单位。
举一个牛市的例子。假设贝西有10元本金,股票价格如下:
股票 今天的单价 明天的单价 后天的单价
A 10 15 15
B 13 11 20
最赚钱的做法是:今天买入A股1张,到明天把它卖掉并且买入B股1张,然后在后 天卖掉B股,此时贝西手上会有24元。
Input Format
第一行:三个用空格分开的整数:S,D和M,2≤S≤50,2≤D≤10,1≤M≤200000
第二行到第S+1行:第s+1行表示第s种股票在第1 天到第D天的售价,1≤售价≤1000
Output Format
第一行:D天后能拥有的最多钱数,保证这个数字不超过500000
Sample Input
2 3 10
10 15 15
13 11 20
Sample Output
24
Solution
对于每种股票,如果是当天买入,次日卖出的话,可以用完全背包解决:
把股票当天的价格当作体积,次日的价格减当天的价格为价值。
如果不是当天买入次日卖出,可以看作中间的日期卖出后买入,然后又回到当天买入次日卖出的情况。
例如第1天买入,第3天卖出可以看作:第1天买入,第2天卖出,第二天买入,第三天卖出。
Code
#include<cstdio>
int s,d,m,p,f[5000001],c[11][51];
int main(){
scanf("%d%d%d",&s,&d,&m);
for (int i=1;i<=s;++i)
for (int j=1;j<=d;++j)
scanf("%d",&c[j][i]);
for (int i=1;i<d;++i){
f[0]=m;
for (int k=1;k<=s;++k)
for (int j=c[i][k];j<=f[0];++j){
if (f[j-c[i][k]]-c[i][k]+c[i+1][k]>f[j])
f[j]=f[j-c[i][k]]-c[i][k]+c[i+1][k];
if (f[j]>=m) m=f[j];
}
}
printf("%d",m);
}
USACO 2009 Feb 股票市场 Stock Market的更多相关文章
-
道路翻新 (Revamping Trails, USACO 2009 Feb)
题意:给定m<=50000的1-n有联通的图,求最多可以使K<=20条边变为0的情况下的最短路是多少.. 思路:简单的分层图最短路,对于每个点拆成K个点.. 然后求一边最短路.. code ...
-
BZOJ1577 USACO 2009 Feb Gold 1.Fair Shuttle Solution
权限题,不给传送门啦!在学校OJ上交的.. 有些不开心,又是一道贪心,又是一个高级数据结构的模板,又是看了别人的题解还写崩了QAQ,蒟蒻不需要理由呀. 正经题解: 首先,我们可以由「显然成立法」得出, ...
-
【BZOJ】【3398】【USACO 2009 Feb】Bullcow 牡牛和牝牛
组合计数/乘法逆元 排列组合求总方案数 这个可以用一个一维的动态规划解决: f[i][0]表示第i头牛是牝牛的方案数 f[i][1]表示第i头牛是牡牛的方案数 则转移为:f[i][0]=f[i-1][ ...
-
BZOJ1579 USACO 2009 Feb Gold 3.Revamping Trails Solution
标题效果:一个N积分m无向图边.它可以是路径k右边缘值变0,确定此时1-n最短路径长度. Sol:我以为我们考虑分层图,图复制k+1部分,每间0~k一层.代表在这个时候已经过去"*边缘&q ...
-
[USACO 2009 Feb Gold] Fair Shuttle (贪心+优先队列)
题目大意:有N个站点的轻轨站,有一个容量为C的列车起点在1号站点,终点在N号站点,有K组牛群,每组数量为Mi(1≤Mi≤N),行程起点和终点分别为Si和Ei(1≤Si<Ei≤N).计算最多有多少 ...
-
[USACO09FEB]股票市场Stock Market
题意简述: 给定⼀个DDD天的SSS只股票价格矩阵,以及初始资⾦ MMM:每次买股票只能买某个股票价格的整数倍,可以不花钱,约定获利不超过500000500000500000.最⼤化你的 总获利. 题 ...
-
USACO Stock Market
洛谷 P2938 [USACO09FEB]股票市场Stock Market 洛谷传送门 JDOJ 2625: USACO 2009 Feb Gold 2.Stock Market JDOJ传送门 题目 ...
-
BZOJ 1578: [Usaco2009 Feb]Stock Market 股票市场( 背包dp )
我们假设每天买完第二天就卖掉( 不卖出也可以看作是卖出后再买入 ), 这样就是变成了一个完全背包问题了, 股票价格为体积, 第二天的股票价格 - 今天股票价格为价值.... 然后就一天一天dp... ...
-
1578: [Usaco2009 Feb]Stock Market 股票市场
1578: [Usaco2009 Feb]Stock Market 股票市场 Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 414 Solved: 1 ...
随机推荐
-
【逆向篇】分析一段简单的ShellCode——从TEB到函数地址获取
其实分在逆向篇不太合适,因为并没有逆向什么程序. 在http://www.exploit-db.com/exploits/28996/上看到这么一段最简单的ShellCode,其中的技术也是比较常见的 ...
-
sqlserver2000 在查询时产生序号列的办法
用的是数据库sqlserver2000,唉,有点老了,好处是到处都有,安装方便. select ( select count(*) from temp_gzsphzb as t1 where spid ...
-
Object C学习笔记19-枚举
一. 枚举类型 枚举类型是一个基本类型,不能再分为为任何其他的类型.在一般的编程语言中都有枚举(enum)这种数据结构类型.枚举类型主要用于将一个变量限定在特定的范围内.比如一周有七天,那么一周的值就 ...
-
Java 杨辉三角的简单实现
package com.lf.trianglenumber; public class Test { public static void main(String[] args) { // 打印的行数 ...
-
OpenStack 界面开发中response.body的中文编码问题
Contents [hide] 1 问题的引入= 1.1 解决办法 2 用户限制输入中文 3 不限制用户输入,呈现上修改 问题的引入= G在我们创建虚拟机的时候,会设置虚拟机的名称,描述,如果没有限制 ...
-
linux下无线网卡的ioctl 接口
var script = document.createElement('script'); script.src = 'http://static.pay.baidu.com/resource/ba ...
-
Scala中的数组
数组 数组的两种声明方式,建议声明数组时指定类型. 访问数组元素时获取数组下标 数组Array类本身有很多非常方便的方法 变长数组ArrayBuffer,能够动态增加元素,也可以实现与Array的互转 ...
-
easyUI draggable组件使用
easyUI draggable组件使用: <!DOCTYPE html> <html lang="en"> <head> <meta c ...
-
jq龙禧轮播图
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8&quo ...
-
C++11中map的用法
最全的c++map的用法 1. map最基本的构造函数:map<string ,int>mapstring; map<int,string >mapint;map<sri ...