传送
题面是不是看不下去了？
我中文题面都看不下去了：
你有(c(0.01 leqslant cleqslant 10 ^ 8))美元现金，但没有股票。给你(m(1 leqslant m leqslant 100))天时间和(n (1leqslant n leqslant 8))支股票供你买卖，要求最后一天结束后不持有任何股票，且剩余的钱最多。买股票不能赊账，只能用现金买。已知第i只股票每天的价格（(0.01)~(999.99)。单位是美元/股）与参数(s_i)和(k_i)，表示一手股票是(s_i(1 leqslant s_i leqslant 10 ^ 6))股，且每天持有的手数不能超过(k_i(1leqslant k_i leqslant k))，其中(k)为每天持有的所有股票总手数上限。每天要么不操作，要么选一只股票，买或卖它的一手股票。(c)和股价均最多包含两位小数（即美分）。最优解保证不超过(10 ^ 9)。要求输出每一天的决策（HOLD表示不变，SELL表示卖，BUY表示买）。
首先股票是一手一手的买，所以每一买的是价格乘以(s_i)，这个预处理直接乘起来就行，简化代码。
看到股票种类很小，会想到状压。状态虽然是(8^8=1.6e7)，但是因为有(k)和(k_i)的限制，实际的状态不到(2 * 10 ^ 4)。所以我们要把这些状态用一遍dfs预处理出来。
因为是八进制状压，有点难办，那么就直接开vector存吧，相反编码的常数还会更大（试了一下，还真这样）。然后用一个map套vector，记录每一个状态的编号。
这样dp的时候第二维就是一个整数编号了。
还要预处理出当前状态买了或卖了一个股票后能转移到的状态，这样转移才是(O(n))的。
至于记录路径，我的做法非常暴力：因为dp状态是二维的，所以直接开一个map，map<m1,m2>两个参数都是一个pair，表示m2状态由m1状态转移过来，然后递归输出路劲即可。
所以时间复杂度是(O(m * S * n))((S)为状态数)。
写的时候思路一定要清晰，然后要有耐心……
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<map>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const db INF = 1e12;
const db eps = 1e-8;
const int maxn = 10;
const int maxm = 105;
const int maxs = 2e4 + 5;
In ll read()
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen("random.in", "r", stdin);
freopen("ha.out", "w", stdout);
#endif
}
db C;
int n, m, K;
struct Node
{
char s[10];
int Max;
db a[maxm];
}t[maxn];
int cnt = 0;
map<vector<int>, int> mp;
map<int, vector<int> > mp2;
#define pr pair<int, int>
#define MP make_pair
#define F first
#define S second
vector<pr> v_sol[maxs], v_buy[maxs];
db dp[maxm][maxs];
vector<int> v;
In void dfs(int x, int num)
{
if(x == n + 1)
{
mp[v] = ++cnt;
mp2[cnt] = v;
return;
}
for(int i = 0; i <= min(K - num, t[x].Max); ++i)
{
v[x] = i;
dfs(x + 1, num + i);
v[x] = 0;
}
}
In void init()
{
mp.clear(); mp2.clear();
v.clear(); cnt = 0;
for(int i = 0; i < maxs; ++i) v_sol[i].clear(), v_buy[i].clear();
for(int i = 1; i <= n + 1; ++i) v.push_back(0);
dfs(1, 0);
for(int i = 1; i <= cnt; ++i)
{
vector<int> tp = mp2[i];
for(int j = 1; j <= n; ++j) if(tp[j])
{
tp[j]--;
v_sol[i].push_back(MP(mp[tp], j));
tp[j]++;
}
int num = 0;
for(int j = 1; j <= n; ++j) num += tp[j];
if(num >= K) continue;
for(int j = 1; j <= n; ++j) if(tp[j] < t[j].Max)
{
tp[j]++;
v_buy[i].push_back(MP(mp[tp], j));
tp[j]--;
}
}
}
struct Path{int F, S, flg;};
map<pr, Path> P;
In void Print(int F, int S)
{
if(!F) return;
Path tp = P[MP(F, S)];
Print(tp.F, tp.S);
if(tp.flg == 0) puts("HOLD");
else printf("%s %s
", tp.flg > 0 ? "BUY" : "SELL", t[abs(tp.flg)].s);
}
In void solve()
{
for(int i = 0; i <= m; ++i)
for(int j = 1; j <= cnt; ++j) dp[i][j] = -INF;
dp[0][1] = C;
for(int i = 0; i < m; ++i)
{
for(int j = 1; j <= cnt; ++j)
{
if(dp[i + 1][j] < dp[i][j])
{
dp[i + 1][j] = dp[i][j];
P[MP(i + 1, j)] = (Path){i, j, 0};
}
for(int k = 0; k < (int)v_sol[j].size(); ++k)
{
int x = v_sol[j][k].F, h = v_sol[j][k].S;
if(dp[i + 1][x] < dp[i][j] + t[h].a[i + 1])
{
dp[i + 1][x] = dp[i][j] + t[h].a[i + 1];
P[MP(i + 1, x)] = (Path){i, j, -h};
}
}
for(int k = 0; k < (int)v_buy[j].size(); ++k)
{
int x = v_buy[j][k].F, h = v_buy[j][k].S;
if(dp[i][j] - t[h].a[i + 1] >= 0 && dp[i + 1][x] < dp[i][j] - t[h].a[i + 1])
{
dp[i + 1][x] = dp[i][j] - t[h].a[i + 1];
P[MP(i + 1, x)] = (Path){i, j, h};
}
}
}
}
printf("%.2lf
", dp[m][1]);
Print(m, 1);
enter;
}
int main()
{
// MYFILE();
while(scanf("%lf%d%d%d", &C, &m, &n, &K) != EOF)
{
for(int i = 1; i <= n; ++i)
{
scanf("%s", t[i].s);
int tp = read(); t[i].Max = read();
for(int j = 1; j <= m; ++j)
{
scanf("%lf", &t[i].a[j]);
t[i].a[j] *= tp;
}
}
init();
solve();
}
return 0;
}