UVa 1412 Fund Management (预处理+状压DP)

题意:题意很难说清楚自己看原文,链接:UVa 1412 Fund Management

析:总体来说如果没有超时的话,这个题不是特别难,但是这个题很容易超时,主要是体现在状态转移时,很容易想到状态方程表示方法,

dp[i][s]表示第 i 天时状态为s时能获得的最大值,转移方程也很容易,三种决策,要么买,要么卖,要么不买不卖,就这三种,但是却不是好转移,

主要是效率不够,所以我们先预处理所有的状态转移,最后直接用就可以了。用的vector和map来存储状态和编号。

代码如下:

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#include <sstream>
#define debug() puts("++++");
#define gcd(a, b) __gcd(a, b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define freopenr freopen("in.txt", "r", stdin)
#define freopenw freopen("out.txt", "w", stdout)
using namespace std; typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-5;
const int maxn = 100000 + 10;
const int mod = 1e6;
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};
const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline bool is_in(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
} const int maxstate = 15000;
int k[10], s[10], kk;
char name[10][100];
double price[10][110];
vector<vector<int> > states;
map<vector<int>, int> mp;
int buy_next[maxstate][10], sell_next[maxstate][10];
double dp[110][maxstate]; void dfs(int stock, vector<int>& lots, int tot){
if(stock == n){
mp[lots] = states.size();
states.push_back(lots);
return ;
}
for(int i = 0; i <= k[stock] && tot + i <= kk; ++i){
lots[stock] = i;
dfs(stock+1, lots, tot + i);
}
} void init(){
vector<int> lots(n);
states.clear();
mp.clear();
dfs(0, lots, 0);
for(int s = 0; s < states.size(); ++s){
int tot = 0;
for(int i = 0; i < n; ++i) tot += states[s][i];
for(int i = 0; i < n; ++i){
buy_next[s][i] = sell_next[s][i] = -1;
if(buy_next[s][i] < k[i] && tot < kk){ // buy
vector<int> tmp = states[s];
++tmp[i];
buy_next[s][i] = mp[tmp];
}
if(states[s][i] > 0){ // sell
vector<int> tmp = states[s];
--tmp[i];
sell_next[s][i] = mp[tmp];
}
}
}
} double c;
int opt[110][maxstate], pre[110][maxstate]; void update(int i, int s, int s2, double v, int o){
if(v > dp[i+1][s2]){
dp[i+1][s2] = v;
opt[i+1][s2] = o;
pre[i+1][s2] = s;
}
} double solve(){
for(int i = 0; i <= m; ++i)
for(int j = 0; j < states.size(); ++j)
dp[i][j] = -inf;
dp[0][0] = c;
for(int i = 0; i < m; ++i)
for(int s = 0; s < states.size(); ++s){
double v = dp[i][s];
if(v < -1) continue;
update(i, s, s, v, 0); //hold
for(int j = 0; j < n; ++j){
if(buy_next[s][j] >= 0 && v >= price[j][i] - 1e-3)
update(i, s, buy_next[s][j], v-price[j][i], j+1); //buy
if(sell_next[s][j] >= 0)
update(i, s, sell_next[s][j], v+price[j][i], -j-1); //sell
}
}
return dp[m][0];
} void print(int i, int s){
if(!i) return ;
print(i-1, pre[i][s]);
if(opt[i][s] == 0) printf("HOLD\n");
else if(opt[i][s] > 0) printf("BUY %s\n", name[opt[i][s]-1]);
else printf("SELL %s\n", name[-opt[i][s]-1], -opt[i][s]-1);
} int main(){
while(scanf("%lf %d %d %d", &c, &m, &n, &kk) == 4){
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 = solve();
printf("%.2f\n", ans);
print(m, 0);
}
return 0;
}
上一篇:Java经典编程题50道之二十


下一篇:Jetty:配置安全