# UVa1412 fund management

#### Train of thought:

The basic idea of this question is clear. d(i,p) is used to express the maximum value of cash when the portfolio is p after i days.
In addition, it should be noted that whether the current cash is enough is not a DAG's longest / shortest path problem when considering buying stocks, because the existence of some edges u - > V depends on the shortest path value from the starting point to the point u. That is to say, this problem can't be "de defined" like the previous DAG problem: if d(i,p) is used to represent the portfolio as p, from the day i to the maximum cash value that can be owned at last, it will be found that the status can't be transferred at all.

1. Fund combination status processed in 9-level system
2. Status number, no need to encode or decode
3. Brush table method
```#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
const int INF = 1<<30;

const int maxn = 8;
const int maxm = 101;
const int maxstate = 15000;

double c, price[maxn][maxm];
int m, n, kk;
char name[maxn][50];
int s[maxn], k[maxn];

vector< vector<int> > states; // states[i]: state I
map< vector<int>, int > ID; // Number corresponding to status

// Number each status
void dfs(int cur_stock, vector<int> &s, int total){
if(cur_stock == n){
ID[s] = states.size();
states.push_back( s );
return;
}
for(int i = 0; i <= k[cur_stock] && total + i <= kk; ++i){
s[cur_stock] = i;
dfs(cur_stock + 1, s, total + i);
}
}

int buy_next[maxstate][maxn], sell_next[maxstate][maxn]; // Indicates the status number transferred to after "buy stock i" and "sell stock i" of status s respectively
void init(){
vector<int> s1(n);
states.clear();
ID.clear();
// Give all stock status numbers
dfs(0, s1, 0);
// Find buy? Next, sell? Next
for(int s = 0; s < states.size(); ++s){
int total = 0;
for(int i = 0; i < n; ++i) total += states[s][i];
for(int i = 0; i < n; ++i){
if(states[s][i] < k[i] && total < kk){
vector<int> newstate = states[s];
++newstate[i];
}
// Sale of the i share
if(states[s][i] > 0){
vector<int> newstate = states[s];
--newstate[i];
sell_next[s][i] = ID[newstate];
}
}
}
}

double d[maxm][maxstate];
int opt[maxm][maxstate], pre[maxm][maxstate];
// The current time (day) state is s, and its operation op may affect the next state s2. If its decision is good, it should be updated in time
void update(int day, int s, int s2, double v, int op){
if(v > d[day+1][s2]){
d[day+1][s2] = v;
opt[day+1][s2] = op;
pre[day+1][s2] = s;
}
}
// Plan
double dp(){
// Initialization
for(int day = 0; day <= m; ++day)
for(int s = 0; s < states.size(); ++s)
d[day][s] = -INF;
//printf("%d\n",states.size());
d[0][0] = c;
for(int day = 0; day < m; ++day){
for(int s = 0; s < states.size(); ++s){
double v = d[day][s];
if(v < -1) continue;
// hold
update(day, s, s, v, 0);
for(int i = 0; i < n; ++i){
if(buy_next[s][i] >= 0 && v >= price[i][day] - 1e-3)
if(sell_next[s][i] >= 0)
update(day, s, sell_next[s][i], v + price[i][day], -i-1); // sell ith stock
}
}
}
return d[m][0];
}

void print_ans(int day, int s){
if(day == 0) return;
print_ans(day-1, pre[day][s]);
if(opt[day][s] == 0) printf("HOLD\n");
else if(opt[day][s] > 0) printf("BUY %s\n",name[opt[day][s]-1]);
else printf("SELL %s\n",name[-opt[day][s]-1]);
}

/*
Total number of test plans
int cnt = 0;
void test(int cur, int total){
if(cur == 8){
++cnt;
return;
}
for(int i = 0; i <= 8 && total+i <= 8; ++i){
test(cur+1, total+i);
}
}
*/

int main()
{
//freopen("in.txt","r",stdin);
// test(0,0);
// Printf (""% d \ n ", CNT); output 12870, the total number of schemes does not exceed 15000
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];
}
}
init();
double ans = dp();
printf("%.2lf\n", ans);
print_ans(m, 0);
}
return 0;
}

```

Posted on Fri, 29 Nov 2019 23:31:14 -0800 by daveeboi