网友投稿 789 2022-09-26
UVA 1412 Fund Management——dp
思路不难，但是写起来真恶心，一定要注意模块化
#include #include #include #include #include #include using namespace std;const int maxn = 2e4;int kase = 0;double c;int m, n, k;struct Date { string name; int s, k; double price[110];}date[10];int tot, cnt[10], nexts[maxn][10][2];map vis;int dfs() { int s = 0; for (int i = 1; i <= n; i++) s = s*9+cnt[i]; if (vis[s]) return vis[s]; int t = vis[s] = ++tot; for (int i = 1; i <= n; i++) { if (cnt[i]) { cnt[i]--; cnt[9]--; nexts[t][i][0] = dfs(); cnt[i]++; cnt[9]++; } if (cnt[i] p[110][maxn];void print(int x, int y) { if (x == 0) return; print(x-1, pre[x][y]); if (p[x][y].second == 0) printf("HOLD\n"); else if (p[x][y].second == -1) { printf("SELL "); cout << date[p[x][y].first].name << endl; } else if (p[x][y].second == 1) { printf("BUY "); cout << date[p[x][y].first].name << endl; }}int main() { //freopen("out.txt", "w", stdout); while (~scanf("%lf %d %d %d", &c, &m, &n, &k)) { for (int i = 1; i <= n; i++) { cin >> date[i].name; scanf("%d %d", &date[i].s, &date[i].k); for (int j = 1; j <= m; j++) { scanf("%lf", &date[i].price[j]); date[i].price[j] *= date[i].s; } } tot = 0; memset(cnt, 0, sizeof(cnt)); memset(nexts, -1, sizeof(nexts)); vis.clear(); dfs(); for (int i = 0; i <= m; i++) { for (int j = 1; j <= tot; j++) dp[i][j] = -1.0; } dp[0][1] = c; for (int i = 0; i < m; i++) { for (int j = 1; j <= tot; j++) { if (dp[i][j] < 0) continue; if (dp[i+1][j] < dp[i][j]) { dp[i+1][j] = dp[i][j]; pre[i+1][j] = j; p[i+1][j].second = 0; } for (int k = 1; k <= n; k++) { int s0 = nexts[j][k][0], s1 = nexts[j][k][1]; if (s0 != -1 && dp[i+1][s0] < dp[i][j]+date[k].price[i+1]) { dp[i+1][s0] = dp[i][j]+date[k].price[i+1]; pre[i+1][s0] = j; p[i+1][s0].first = k; p[i+1][s0].second = -1; } if (s1 != -1 && dp[i+1][s1] < dp[i][j]-date[k].price[i+1]) { dp[i+1][s1] = dp[i][j]-date[k].price[i+1]; pre[i+1][s1] = j; p[i+1][s1].first = k; p[i+1][s1].second = 1; } } } } if (kase++) printf("\n"); printf("%.2lf\n", dp[m][1]); print(m, 1); } return 0;}
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论，来抢沙发吧~
暂时没有评论，来抢沙发吧~