状压dp

要再看看  例题9-17

/*
// UVa1412 Fund Management
// 本程序会超时,只是用来示范用编码/解码的方法编写复杂状态动态规划的方法
// Rujia Liu
#include<cstdio>
#include<cstring>
#include<map>
using namespace std; const double INF = 1e30;
const int maxn = 8;
const int maxm = 100 + 5; map<int, double> d[maxm];
map<int, int> opt[maxm], prevv[maxm];
int m, n, s[maxn], k[maxn], kk;
double c, price[maxn][maxm];
char name[maxn][10]; int encode(int* portfolio) {
int h = 0;
for(int i = 0; i < n; i++) h = h * 9 + portfolio[i];
return h;
} int decode(int h, int* portfolio) {
int totlot = 0;
for(int i = n-1; i >= 0; i--) {
portfolio[i] = h % 9;
totlot += portfolio[i];
h /= 9;
}
return totlot;
} void update(int oldh, int day, int h, double v, int o) {
if(d[day].count(h) == 0 || v > d[day][h]) {
d[day][h] = v;
opt[day][h] = o;
prevv[day][h] = oldh;
}
} double dp() {
int portfolio[maxn];
d[0][0] = c;
for(int day = 0; day < m; day++)
for(map<int, double>::iterator it = d[day].begin(); it != d[day].end(); it++) {
int h = it->first;
double v = it->second;
int totlot = decode(h, portfolio); update(h, day+1, h, v, 0); // HOLD
for(int i = 0; i < n; i++) {
if(portfolio[i] < k[i] && totlot < kk && v >= price[i][day] - 1e-3) {
portfolio[i]++;
update(h, day+1, encode(portfolio), v - price[i][day], i+1); // BUY
portfolio[i]--;
}
if(portfolio[i] > 0) {
portfolio[i]--;
update(h, day+1, encode(portfolio), v + price[i][day], -i-1); // SELL
portfolio[i]++;
}
}
}
return d[m][0];
} void print_ans(int day, int h) {
if(day == 0) return;
print_ans(day-1, prevv[day][h]);
if(opt[day][h] == 0) printf("HOLD\n");
else if(opt[day][h] > 0) printf("BUY %s\n", name[opt[day][h]-1]);
else printf("SELL %s\n", name[-opt[day][h]-1]);
} int main() {
int kase = 0;
while(scanf("%lf%d%d%d", &c, &m, &n, &kk) == 4) {
if(kase++ > 0) printf("\n");
for(int i = 0; i < n; i++) {
scanf("%s%d%d", name[i], &s[i], &k[i]);
for(int j = 0; j < m; j++) { scanf("%lf", &price[i][j]); price[i][j] *= s[i]; }
}
for(int i = 0; i <= m; i++) { d[i].clear(); opt[i].clear(); prevv[i].clear(); } double ans = dp();
printf("%.2lf\n", ans);
print_ans(m, 0);
}
return 0;
}
*/ #include<cstdio>
#include<cstring>
#include<vector>
#include<map>
using namespace std; const double INF = 1e30;
const int maxn = ;
const int maxm = + ;
const int maxstate = ; int m, n, s[maxn], k[maxn], kk;
double c, price[maxn][maxm];
char name[maxn][]; double d[maxm][maxstate];
int opt[maxm][maxstate], prevv[maxm][maxstate]; int buy_next[maxstate][maxn], sell_next[maxstate][maxn];
vector<vector<int> > states;
map<vector<int>, int> ID; void dfs(int stock, vector<int>& lots, int totlot) {
if(stock == n) {
ID[lots] = states.size();
states.push_back(lots);
}
else for(int i = ; i <= k[stock] && totlot + i <= kk; i++) {
lots[stock] = i;
dfs(stock+, lots, totlot + i);
}
} void init() {
vector<int> lots(n);
states.clear();
ID.clear();
dfs(, lots, );
for(int s = ; s < states.size(); s++) {
int totlot = ;
for(int i = ; i < n; i++) totlot += states[s][i];
for(int i = ; i < n; i++) {
buy_next[s][i] = sell_next[s][i] = -;
if(states[s][i] < k[i] && totlot < kk) {
vector<int> newstate = states[s];
newstate[i]++;
buy_next[s][i] = ID[newstate];
}
if(states[s][i] > ) {
vector<int> newstate = states[s];
newstate[i]--;
sell_next[s][i] = ID[newstate];
}
}
}
} void update(int day, int s, int s2, double v, int o) {
if(v > d[day+][s2]) {
d[day+][s2] = v;
opt[day+][s2] = o;
prevv[day+][s2] = s;
}
} double dp() {
for(int day = ; day <= m; day++)
for(int s = ; s < states.size(); s++) d[day][s] = -INF; d[][] = c;
for(int day = ; day < m; day++)
for(int s = ; s < states.size(); s++) {
double v = d[day][s];
if(v < -) continue; update(day, s, s, v, ); // HOLD
for(int i = ; i < n; i++) {
if(buy_next[s][i] >= && v >= price[i][day] - 1e-)
update(day, s, buy_next[s][i], v - price[i][day], i+); // BUY
if(sell_next[s][i] >= )
update(day, s, sell_next[s][i], v + price[i][day], -i-); // SELL
}
}
return d[m][];
} void print_ans(int day, int s) {
if(day == ) return;
print_ans(day-, prevv[day][s]);
if(opt[day][s] == ) printf("HOLD\n");
else if(opt[day][s] > ) printf("BUY %s\n", name[opt[day][s]-]);
else printf("SELL %s\n", name[-opt[day][s]-]);
} int main() {
int kase = ;
while(scanf("%lf%d%d%d", &c, &m, &n, &kk) == ) {
if(kase++ > ) printf("\n"); for(int i = ; i < n; i++) {
scanf("%s%d%d", name[i], &s[i], &k[i]);
for(int j = ; j < m; j++) { scanf("%lf", &price[i][j]); price[i][j] *= s[i]; }
}
init(); double ans = dp();
printf("%.2lf\n", ans);
print_ans(m, );
}
return ;
}

最新文章

  1. Poco C++ MySQl demo
  2. sqlserver开启&#39;xp_cmdshell&#39;命令
  3. 是什么时候开始学习gulp了
  4. [转]SQLServer跨服务器访问数据库(openrowset/opendatasource/openquery)
  5. mui
  6. Intellij IDEA svn的使用记录
  7. 2016年6月25日 星期六 --出埃及记 Exodus 14:22
  8. 为什么在Spring的配置里,最好不要配置xsd文件的版本号
  9. 在Activity之间传递数据—简单数据/Bundle
  10. MNIST-NameError: name ‘input_data’ is not defined解决办法
  11. Swift基础之集成单选按钮横竖两种样式
  12. 题解 P4692 【[Ynoi2016]谁的梦】
  13. debian9升级安装到python3.6和pip3.6
  14. SQL Server中与IO相关的等待类型:IO_COMPLETION和PAGEIOLATCH_*
  15. 5款 Mac 常用PDF阅读和编辑软件推荐
  16. AutoFac在MVC中的使用
  17. ueditor保存出现 从客户端(Note=&quot;&lt;p&gt;12345&lt;/p&gt;&quot;)中检测到有潜在危险的 Request.Form 值
  18. Visual Studio 2017 版本 15.5.5
  19. python学习笔记_week20
  20. babel 基本

热门文章

  1. MYSQL数据库学习----MYSQL函数
  2. 任务31:课时介绍 &amp; 任务32:Cookie-based认证介绍 &amp;任务33:34课 :AccountController复制过来没有移除[Authorize]标签
  3. JDK8 Lamdba表达式转换成Map,value为null问题
  4. poj 3294 Life Forms【SA+二分】
  5. 屏蔽QQ黄钻官方团队送礼物的方法
  6. pip 国内安装镜像源
  7. Mantis优化改造(技术篇)
  8. visual studio各版本下载
  9. 《统计学习方法》笔记三 k近邻法
  10. 喵哈哈村的魔法考试 Round #3 (Div.2) ABCDE