题目大意

Frank从个人投资者获得了c美元的资金,可用于m天的投资。
Frank可以对n(n<=8)支股票进行投资。对于每一支股票:都有一个交易上限si,表示一天最多能交易的股数;还有一个上限ki,表示Frank最多可持有的股数。对于所有种类的股票,同样有一个上限k表示Frank可同时持有的最大股数。
股票的交易还满足一下要求:
1>一天最多只能进行一次交易(你也可以不交易);
2>若要对第i支股票进行买进或卖出,只能一次性买或卖Si股;
3>所有的交易都是在Frank有足够的资金的条件下完成的;
4>当m天过去后,Frank的资金必须全部转化为现金,不能放在股票市场里,(m天之内,股票必须全部卖出)。
现在,给出每一支股票的每一天的价格,要求你计算出Frank能回收的资金的最大值,并给出每一天的具体的操作方法。

思路

先考虑考虑暴力。最后一天要把所有资产转化为现金,我们要枚举前一天在各个股票上各投了多少股(我们把它称为状态state),以及剩余的现金量。用股市上的资产加上剩余的现金量便是所求,然后同理枚举前一天的前一天。但是我们发现,天数和state一定时,剩余的现金量愈大,这种情况就越优。于是我们定义DP[day][state]为第day天还未投股时投股状态state时的最大剩余现金量。递归式为:

DP[day][state] = max{operate(DP[day-1][prevState], stock)|operate∈{Buy, Sell, Hold}, operate后prevState==state,P满足}

P=

  1. 0<=eachStockLot<=EachStockLotLimit
  2. 0<=Sum(stockLot)<=TotLotLimit
  3. leftCash>=0

同时满足。

然后按天刷表即可。

各个函数的功能

InitState:将所有满足(1)、(2)的状态都枚举出来。
SetGraph:从递归式中可以看出,我们应当通过该函数设置出所有的BuyNext,SellNext。很多条件限制在SetState中已经满足了,所以我们用map中的count函数便可判断将要生成的状态是否成立了。
DP:根据递归式递推。
Update:在DP中调用,可节省大量重复代码。看看潜在的MaxCash能否进行“放松”,若能,则为后一个MaxCash重新设置其MaxCash值、前继状态编号、操作的股票、和进行的操作。

状态压缩

如何保存state呢?我们发现总股数和每股最多持股数最多只有(1<<3)==8,所以一个股票买的张数4位整数便足够,4*8==32,整数32子节,所以把一个整数每4个字节表示一个股票买的张数,那么一个整数便可以表示出所有股票的状态。这便是十进制状态压缩。

注意

  • 每个状态都要有个编号,否则状态总数约为1<<32,太多了。
  • 分清curS和curID.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <bitset>
#include <cstdarg>
using namespace std;
//#define test const int MAXSTOCK = 8, MAXDAY = 110, MAXID = 20000, INF = 0x3f3f3f3f;
double BeginMoney;
int TotDay, TotStock, LotLimit;
vector<int> State;
map <int, int> Sid;
int IdCnt = 0;
double DImaxcash[MAXDAY][MAXID];//某天某状态进行操作前的最大现金值
int ISbuynextI[MAXID][MAXSTOCK], ISsellnextI[MAXID][MAXSTOCK];
int DIprevI[MAXDAY][MAXID], DIaction[MAXDAY][MAXID], DIdeltaS[MAXDAY][MAXID];
char* Ans[] = { "HOLD","BUY","SELL" }; struct Stock
{
char name[20];
int eachLot, totLotCnt;
double dailyPrice[MAXDAY];
};
Stock Stocks[MAXSTOCK]; void Reset()
{
State.clear();
Sid.clear();
memset(DImaxcash, 0, sizeof(DImaxcash));
memset(ISbuynextI, 0, sizeof(ISbuynextI));
memset(ISsellnextI, 0, sizeof(ISsellnextI));
memset(DIprevI, 0, sizeof(DIprevI));
memset(DIaction, 0, sizeof(DIaction));
memset(DIdeltaS, 0, sizeof(DIdeltaS));
memset(Stocks, 0, sizeof(Stocks));
IdCnt = 0;
} #define SetState(S, s, i) S = (S & (~(0xf<<(i*4))) | ((s)<<(i*4)))
#define ClearState(S, i) (S &= (~(0xf<<(i*4))))
#define GetState(S, i) (((S) >> (i*4)) & 0xf) void PlusState(int &S, int i, int plus)
{
int temp = GetState(S, i) + plus;
SetState(S, temp, i);
} void InitState(int stockCnt, int& temp, int prevTotal)
{
if (stockCnt == TotStock)
{
State.push_back(temp);
Sid[temp] = IdCnt++;
return;
}
for (int i = 0; i <= Stocks[stockCnt].totLotCnt; i++)
{
if (prevTotal + i <= LotLimit)
{
SetState(temp, i, stockCnt);
InitState(stockCnt + 1, temp, prevTotal + i);
ClearState(temp, stockCnt);
}
}
} void SetGraph()
{
for (int id= 0; id < IdCnt; id++)
{
for (int toStock = 0; toStock < TotStock; toStock++)
{
ISsellnextI[id][toStock] = ISbuynextI[id][toStock] = -1;
int temp = State[id];
PlusState(temp, toStock, 1);
if (Sid.count(temp) > 0)
ISbuynextI[id][toStock] = Sid[temp];
if (GetState(State[id],toStock))
{
temp = State[id];
PlusState(temp, toStock, -1);
ISsellnextI[id][toStock] = Sid[temp];
}
}
}
} void Update(int day, int id, int nextID, int toStock, double leftCash, int action)
{
if (leftCash > DImaxcash[day + 1][nextID])
{
DImaxcash[day + 1][nextID] = leftCash;
DIprevI[day + 1][nextID] = id;
DIdeltaS[day + 1][nextID] = toStock;
DIaction[day + 1][nextID] = action;
}
} void DP()
{
for (int i = 0; i <= TotDay; i++)
for (int j = 0; j < IdCnt; j++)
DImaxcash[i][j] = -INF; DImaxcash[0][0] = BeginMoney;
for (int day = 0; day <= TotDay; day++)
for (int curID = 0; curID < IdCnt; curID++)
{
if (DImaxcash[day][curID] == -INF)
continue; for (int toStock = 0; toStock < TotStock; toStock++)
Update(day, curID, curID, 0, DImaxcash[day][curID], 0); for (int toStock = 0; toStock < TotStock; toStock++)
{
if (ISbuynextI[curID][toStock] != -1 && DImaxcash[day][curID] >= Stocks[toStock].dailyPrice[day] * Stocks[toStock].eachLot - 0.001)
{
double leftCash = DImaxcash[day][curID] - Stocks[toStock].dailyPrice[day] * Stocks[toStock].eachLot;
Update(day, curID, ISbuynextI[curID][toStock], toStock, leftCash, 1);
}
if (ISsellnextI[curID][toStock] != -1 && GetState(State[curID], toStock) > 0)
{
double leftCash = DImaxcash[day][curID] + Stocks[toStock].dailyPrice[day] * Stocks[toStock].eachLot;
Update(day, curID, ISsellnextI[curID][toStock], toStock, leftCash, 2);
}
}
}
} void print(int day, int id)
{
if (day == 0)
return;
print(day - 1, DIprevI[day][id]);
if (DIaction[day][id] == 0)
printf("HOLD\n");
else
printf("%s %s\n", Ans[DIaction[day][id]], Stocks[DIdeltaS[day][id]].name);
} int main()
{
//TestBinary();
freopen("c:\\noi\\source\\input.txt", "r", stdin);
bool isFirst = true;
while (~scanf("%lf%d%d%d", &BeginMoney, &TotDay, &TotStock, &LotLimit))
{
Reset();
for (int i = 0; i < TotStock; i++)
{
scanf("%s%d%d", &Stocks[i].name, &Stocks[i].eachLot, &Stocks[i].totLotCnt);
for (int j = 0; j < TotDay; j++)
scanf("%lf", &Stocks[i].dailyPrice[j]);
}
int temp = 0;
InitState(0, temp, 0);
SetGraph();
DP();
if (!isFirst)
printf("\n");
isFirst = false;
printf("%.2f\n", DImaxcash[TotDay][0]);
print(TotDay, 0);
}
return 0;
}

  

最新文章

  1. js整理
  2. Codeforces Round #258 (Div. 2)
  3. php服务器版本更新工具up2server
  4. 基础篇之 Create Type
  5. Codeforces Round #346 (Div. 2) E F
  6. [深入Python]__new__和__init__
  7. Xcode error: conflicting types for &#39;XXXX&#39;
  8. C# 对Excel 单元格格式, 及行高、 列宽、 单元格边框线、 冻结设置
  9. 关于linux下零散的东西 --慢慢补充
  10. 《深入理解linux内核》第三章 进程
  11. 手动通过Lucene判断该pom文件中jar是否存在,子依赖没判断
  12. ImageView一例
  13. 1.0.1-学习Opencv与MFC混合编程之---播放AVI视频
  14. hiero_v2.0的下载安装和使用
  15. js实现两种实用的排序算法——冒泡、快速排序
  16. stm32定时器输出移相PWM(非主从模式)
  17. 第9条:try-with-resources优于try-finally
  18. Python循环结构用法
  19. mysql从5.5直接升级到5.7后,执行mysql_upgrade速度很慢且执行结束后数据目录大小增加一倍及 mysqlpump备份出现1577错误
  20. centos6.8上yum安装zabbix3.2

热门文章

  1. jar 包中文乱码注释显示问题解决方案
  2. Flex使用总结
  3. 在窗体中把DataGridView中的数据导出Excel
  4. (转载)实例详解Android快速开发工具类总结
  5. 修改Switch 的颜色
  6. Eclipse安装配置——For Java
  7. 【sqli-labs】 less4 GET - Error based - Double Quotes - String (基于错误的GET双引号字符型注入)
  8. Hadoop分布式文件系统架构部署
  9. mysql主主同步
  10. echarts 中 请求后台改变数据