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想通過合理投資銀行理財(cái)產(chǎn)品達(dá)到收益最大化。已知小A在未來一段時(shí)間中的收入情況，描述為兩個(gè)長度為n的整數(shù)數(shù)組dates和earnings，表示在 第dates[i]天小A收入earnings[i]元（0<=i<n）。銀行推出的理財(cái)產(chǎn)品均為周期和收益確定的，可描述為長度為m的三個(gè) 整數(shù)數(shù)組start、finish和interest_rates, 若購買理財(cái)產(chǎn)品i（0<=i<m），需要在第start[i]天投入本金，在第finish[i]天可取回本金和收益，在這期間本金和收益都 無法取回，收益為本金*interest_rates[i]/100.0。當(dāng)天取得的收入或理財(cái)產(chǎn)品到期取回的本金當(dāng)天即可購買理財(cái)產(chǎn)品（注意：不考慮復(fù) 利，即購買理財(cái)產(chǎn)品獲得的收益不能用于購買后續(xù)的理財(cái)產(chǎn)品）。假定閑置的錢沒有其他收益，如活期收益等，所有收益只能通過購買這些理財(cái)產(chǎn)品獲得。求小A可 以獲得的最大收益。

限制條件:
1<=n<=2500
1<=m<=2500
對(duì)于任意i（0<=i<n）,1<=dates[i]<=100000,1<=earnings[i]<=100000, dates中無重復(fù)元素。
對(duì)于任意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行，每行為兩個(gè)以空格分隔的整數(shù)，依次為date和earning
之后連續(xù)m行，每行為三個(gè)以空格分隔的整數(shù)，依次為start, finish和interest_rate

?

Output 對(duì)第i組數(shù)據(jù)，i從1開始計(jì)，輸出
Case #i:
收益數(shù)值，保留小數(shù)點(diǎn)后兩位，四舍五入。

?

Sample Input 2 1 2 1 10000 1 100 5 50 200 10 2 2 1 10000 5 20000 1 5 6 5 9 7

?

Sample Output Case #1: 1000.00 Case #2: 2700.00

?

Source 2014年百度之星程序設(shè)計(jì)大賽 - 初賽（第二輪） 題目分析： 這里我們忽略利率底下的100，將其放在最后計(jì)算（因?yàn)樗械睦娑家?00，索性放到最后）。 這樣，題目可以理解為， 給你n份錢，每份錢有一個(gè)價(jià)值val[i]，每份錢所給的時(shí)間之后有x個(gè)區(qū)間，每個(gè)區(qū)間有一個(gè)價(jià)值w[i]，選擇互不相交的區(qū)間，這份錢能帶來收益即為　　　val[i] * 　　sum(w[j])（其中所有的j互不相交）。　　 所有錢帶來的收益即為：sum(val[i] * sum(w[j]))（其中所有的j互不相交）。 那么怎么樣才能使得收益達(dá)到最大？？ 設(shè)dp[i]為從第i個(gè)時(shí)間點(diǎn)開始往后選擇的所有不想交的區(qū)間的價(jià)值總和的最大值，我們假設(shè)第i個(gè)時(shí)間點(diǎn)之后的dp[j]已經(jīng)得到，那么dp[i] = max(dp[j]）+ w[i]； 則最大利益即 ans = sum(val[i] * dp[i]) / 100.0;（不要忘了將利率底下的100除掉） 這里我們用鏈?zhǔn)角跋蛐谴鎯?chǔ)屬于以每個(gè)時(shí)間點(diǎn)為起點(diǎn)的每個(gè)區(qū)間的終點(diǎn)和價(jià)值。（并小小的加一個(gè)輸入優(yōu)化玩耍一下~) 代碼如下： #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; } HDU 4833

?

轉(zhuǎn)載于:https://www.cnblogs.com/ac-luna/p/3752936.html

總結(jié)

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

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