正文 

当前位置： 首页 > java > java教程

bzoj1578/usaco2009febstockmarket股票市场——完全背包

Child-Single Child-Single     2022-09-23     238

关键词：

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
 
每一天的收益可以看成今天买明天卖（如果不是明天卖就先卖再卖），这样就能转变成对每一天分别做完全背包了。
注意每天过后手中的资金（即体积）会变为mx+f[mx]。-->在这一天资金为mx时最大获利。
代码：
技术分享 
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define mem(a,p) memset(a,p,sizeof(a))
 5 int read(){
 6     int ans=0,f=1;char c=getchar();
 7     while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
 8     while(c>=‘0‘&&c<=‘9‘){ans=ans*10+c-48;c=getchar();}
 9     return ans*f;
10 }
11 inline int max(int x,int y){return x>y?x:y;}
12 int pr[55][15],f[500005];
13 int main(){
14     int s=read(),d=read(),m=read();
15     for(int i=1;i<=s;i++)
16         for(int j=1;j<=d;j++)pr[i][j]=read();
17     for(int i=1;i<d;i++){
18         mem(f,0);
19         for(int j=1;j<=s;j++){
20             for(int k=pr[j][i];k<=m;k++){
21                 f[k]=max(f[k],f[k-pr[j][i]]+pr[j][i+1]-pr[j][i]);
22             }
23         }
24         m+=f[m];
25     }
26     printf("%d",m);
27     return 0;
28 }
29
bzoj1578

 

 

[bzoj1578][usaco2009feb]stockmarket股票市场（dp）

传送门 可以看出第一天买，第三天卖==第一天买，第二天卖完再买，第三天卖所以我们只考虑前一天买，后一天卖即可那么有按天数来划分f[i][j]表示前i天，共有j元，最大的盈利第一维可以省去那么有两种选择，不买或者前... 查看详情

bzoj1877:[sdoi2009]晨跑

二次联通门: BZOJ1877:[SDOI2009]晨跑     /*BZOJ1877:[SDOI2009]晨跑拆点+费用流*/#include<cstdio>#include<iostream>#definergregisterinlinevoidread(int&n){rgcharc=getchar() 查看详情

bzoj1800:[ahoi2009]fly飞行棋

二次联通门: BZOJ1800:[Ahoi2009]fly飞行棋    /*BZOJ1800:[Ahoi2009]fly飞行棋乱搞一下就好*/#include<cstdio>#include<iostream>#definergregisterinlinevoidread(int&n){rgintc=getchar( 查看详情

bzoj1296:[scoi2009]粉刷匠

                  BZOJ1296:[SCOI2009]粉刷匠         Descriptionwindy 查看详情

bzoj1449[jsoi2009]球队收益

TimeLimit: 5Sec  MemoryLimit: 64MBSubmit: 741  Solved: 423DescriptionInputOutput一个整数表示联盟里所有球队收益之和的最小值。SampleInput331021111010133122331SampleOutput43HINTSource&n 查看详情

bzoj1562:[noi2009]变换序列

1562:[NOI2009]变换序列TimeLimit:5Sec  MemoryLimit:64MBSubmit:2030  Solved:1026[Submit][Status][Discuss]DescriptionInputOutputSampleInput511221SampleOutput12403HINT 30%的数据中N≤50；60% 查看详情

bzoj1443:[jsoi2009]游戏game

1443:[JSOI2009]游戏GameTimeLimit:10SecMemoryLimit:162MBSubmit:1334Solved:613[Submit][Status][Discuss]DescriptionInput输入数据首先输入两个整数N,M，表示了迷宫的边长。接下来N行，每行M个字符，描述了迷宫。Output若小AA能够赢得游戏，则输出一行"WIN... 查看详情

bzoj1486[hnoi2009]最小圈

bzoj1486[HNOI2009]最小圈题意：定义图中一个环的平均值为环上边权和除以（浮点除法）边数，求一个图中的最小环平均值，保留8位。n≤3000，m≤10000，有负权边。题解：这就是比较明显的01分数规划了，见bzoj1690。同时根据题解二... 查看详情

[bzoj1355][baltic2009]radiotransmission

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1355[Baltic2009]RadioTransmissionTimeLimit: 10Sec  MemoryLimit: 64MBSubmit: 912  Solved: 626[Submit][Status] 查看详情

bzoj1433:[zjoi2009]假期的宿舍

1433:[ZJOI2009]假期的宿舍TimeLimit:10Sec  MemoryLimit:162MBSubmit:3134  Solved:1324[Submit][Status][Discuss]DescriptionInputOutputSampleInput13110010011100100SampleOutputˆˆHIN 查看详情

bzoj1433:[zjoi2009]假期的宿舍

1433:[ZJOI2009]假期的宿舍TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 2286  Solved: 969[Submit][Status][Discuss]DescriptionInputOutputSampleInput13110010011100100Samp 查看详情

bzoj1303:[cqoi2009]中位数图

二次联通门: BZOJ1303:[CQOI2009]中位数图    /*BZOJ1303:[CQOI2009]中位数图对于一个数若当前数大于中位数，则记为1小于中位数，记为-1，等于则记为0对原数列做一个前缀和观察发现，若一段区间符合要求则该段区间内... 查看详情

[bzoj1486][hnoi2009]最小圈

[BZOJ1486][HNOI2009]最小圈试题描述输入见“试题描述”输出见“试题描述”输入示例45125235315243413输出示例3.66666667数据规模及约定见“试题描述”题解分数规划，二分答案x后每条边的边权减去x，若有负环则表明答案小于等于x。#inc... 查看详情

bzoj1296scoi2009粉刷匠

1296:[SCOI2009]粉刷匠TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 1479  Solved: 837[id=1296"style="color:blue;text-decoration:none">Submit][Status][Discuss]Descript 查看详情

bzoj1452:[jsoi2009]count

DescriptionInputOutputSampleInputSampleOutput12HINT  题目传送门 话说这好像是我第一次做树状数组的题树状数组裸题，还是二维的，多一层for而已 代码如下：#include<cmath>#include<cstdio>#include<cstring>#include< 查看详情

bzoj1876:[sdoi2009]supergcd

1876:[SDOI2009]SuperGCDTimeLimit: 4Sec  MemoryLimit: 64MBSubmit: 2999  Solved: 1011[Submit][Status][Discuss]DescriptionShengbill有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的GCD（最大 查看详情

bzoj1876[sdoi2009]supergcd

1876:[SDOI2009]SuperGCDTimeLimit: 4Sec  MemoryLimit: 64MBSubmit: 3744  Solved: 1349[Submit][Status][Discuss]DescriptionShengbill有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的GCD（最大 查看详情

[bzoj1297][scoi2009]迷路

1297:[SCOI2009]迷路TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 1418  Solved: 1017[Submit][Status][Discuss]Descriptionwindy在有向图中迷路了。该有向图有N个节点，windy从节点0出发，他必须恰好在T时刻 查看详情