Best Financing

Time Limit: 20000/10000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 120????Accepted Submission(s): 24


Problem Description
小A想通過合理投資銀行理財產(chǎn)品達(dá)到收益最大化。已知小A在未來一段時間中的收入情況，描述為兩個長度為n的整數(shù)數(shù)組dates和earnings，表示在第dates[i]天小A收入earnings[i]元（0<=i<n）。銀行推出的理財產(chǎn)品均為周期和收益確定的，可描述為長度為m的三個整數(shù)數(shù)組start、finish和interest_rates, 若購買理財產(chǎn)品i（0<=i<m），需要在第start[i]天投入本金，在第finish[i]天可取回本金和收益，在這期間本金和收益都無法取回，收益為本金*interest_rates[i]/100.0。當(dāng)天取得的收入或理財產(chǎn)品到期取回的本金當(dāng)天即可購買理財產(chǎn)品（注意：不考慮復(fù)利，即購買理財產(chǎn)品獲得的收益不能用于購買后續(xù)的理財產(chǎn)品）。假定閑置的錢沒有其他收益，如活期收益等，所有收益只能通過購買這些理財產(chǎn)品獲得。求小A可以獲得的最大收益。
限制條件:
1<=n<=2500
1<=m<=2500
對于任意i（0<=i<n）,1<=dates[i]<=100000,1<=earnings[i]<=100000, dates中無重復(fù)元素。
對于任意i（0<=i<m）,1<=start[i]<finish[i]<=100000, 1<=interest_rates[i]<=100。
?
?
Input
第一行為T (T<=200)，表示輸入數(shù)據(jù)組數(shù)。
每組數(shù)據(jù)格式如下：
第一行是n m
之后連續(xù)n行，每行為兩個以空格分隔的整數(shù)，依次為date和earning
之后連續(xù)m行，每行為三個以空格分隔的整數(shù)，依次為start, finish和interest_rate
?
?
Output
對第i組數(shù)據(jù)，i從1開始計，輸出
Case #i:
收益數(shù)值，保留小數(shù)點后兩位，四舍五入。
?
?
Sample Input
21 21 100001 100 550 200 102 21 100005 200001 5 65 9 7
?
?
Sample Output
Case #1:1000.00Case #2:2700.00
?
?
Source
2014年百度之星程序設(shè)計大賽 - 初賽（第二輪）
?
?
?
題目分析：
　　
這里我們忽略利率底下的100，將其放在最后計算（因為所有的利益都要除以100，索性放到最后）。
　　
這樣，題目可以理解為， 給你n份錢，每份錢有一個價值val[i]，每份錢所給的時間之后有x個區(qū)間，每個區(qū)間有一個價值w[i]，選擇互不相交的區(qū)間，這份錢能帶來收益即為　　　val[i] * 　　sum(w[j])（其中所有的j互不相交）。　　
　　
所有錢帶來的收益即為：sum(val[i] * sum(w[j]))（其中所有的j互不相交）。
?
那么怎么樣才能使得收益達(dá)到最大？？
?
設(shè)dp[i]為從第i個時間點開始往后選擇的所有不想交的區(qū)間的價值總和的最大值，我們假設(shè)第i個時間點之后的dp[j]已經(jīng)得到，那么dp[i] = max(dp[j]）+ w[i]；
?
則最大利益即 ans = sum(val[i] * dp[i]) / 100.0;（不要忘了將利率底下的100除掉）
?
這里我們用鏈?zhǔn)角跋蛐谴鎯儆谝悦總€時間點為起點的每個區(qū)間的終點和價值。
?

代碼如下：

#include <stdio.h> #include <string.h> #include <algorithm> #define max(a, b) ((a) > (b) ? (a) : (b)) using namespace std; const int O = 100005; typedef struct E{int v, n, e; }E; E edge[O]; int Adj[O], l; int val[O], dp[O]; int t, n, m, cas; int d, e, s, f; void addedge(int u, int v, int e){edge[l].v = v; edge[l].e = e; edge[l].n = Adj[u]; Adj[u] = l++; } int read(){char ch = ' ';int x = 0;while(ch < '0' || ch > '9') ch = getchar();while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x; } void work(){memset(val, 0, sizeof(val));memset(Adj, -1, sizeof(Adj));l = 0;n = read(); m = read();while(n--){d = read(); e = read();val[d] += e;}while(m--){s = read(); f = read(); e = read();addedge(s, f, e);}dp[100001] = 0;double ans = 0;for(int i = 100000; i; --i){dp[i] = dp[i + 1];for(int j = Adj[i]; ~j; j = edge[j].n){dp[i] = max(dp[i], dp[edge[j].v] + edge[j].e);}ans += dp[i] * val[i];}printf("%.2f\n", ans / 100); } int main(){for(t = read(), cas = 1; cas <= t; ++cas){printf("Case #%d:\n", cas);work();}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【HDU】 4833 Best Financing DP的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。