原題：http://acm.hdu.edu.cn/showproblem.php?pid=4833

題意：中文題不解釋...

解題思路：

首先以interest_rates為費(fèi)用建圖跑費(fèi)用流是比較容易想到的，于是比賽中我T了10幾發(fā)...

那么我們考慮另外一種思路，把本金分成1塊錢1塊錢來(lái)考慮。

對(duì)于在時(shí)間d得到的錢，他只能在d時(shí)間之后的理財(cái)進(jìn)行投資，收回之后再在更后面進(jìn)行投資，最終帶來(lái)的總收益等于 投資的理財(cái)?shù)膇nterest_rates之和 / 100

所以我們可以設(shè) dp[i] 表示從時(shí)間i開始，對(duì)從時(shí)間 i 之后開始的理財(cái)進(jìn)行投資，可以獲得的最大收益系數(shù)和，首先如果我們無(wú)視從 i 時(shí)刻開始的理財(cái)，dp[i] 就等于 dp[i+1]

否則如果有一個(gè)從時(shí)間 i 開始，到時(shí)間 j 結(jié)束的理財(cái) x，對(duì)其投資后，dp[i] = dp[j] + interest_rates[x]，所以我們可以枚舉從時(shí)刻 i 開始的理財(cái)，對(duì)dp[i] 進(jìn)行優(yōu)化

得到dp[]之后，對(duì)于在時(shí)刻 i 獲得的本金，其總收益就是 本金 * dp[i] / 100

代碼：

<span style="font-family:Courier New;">#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <string> #include <vector> using namespace std;#define LL long long #define MP make_pair #define eps 1e-8 #define mod 1000000007#define mxn 2505int d[mxn], e[mxn], s[mxn], t[mxn], k[mxn]; LL dp[100005], val[100005]; vector<int> nxt[100005], K[100005];int main() {int T, n, m, cas = 0;scanf( "%d", &T );while( T-- ) {scanf( "%d%d", &n, &m );memset(val, 0, sizeof(val));for( int i = 0; i < n; ++i ) {scanf( "%d%d", d + i, e + i );val[d[i]] += e[i];}for( int i = 0; i <= 100000; ++i ) nxt[i].clear(), K[i].clear();for( int i = 0; i < m; ++i ) {scanf( "%d%d%d", s + i, t + i, k + i );nxt[s[i]].push_back(t[i]);K[s[i]].push_back(k[i]);}dp[100001] = 0;double ans = 0;for( int i = 100000; i >= 1; --i ) {dp[i] = dp[i+1];for( int j = 0; j < nxt[i].size(); ++j )dp[i] = max(dp[i], dp[nxt[i][j]] + K[i][j]);ans += dp[i] * val[i];}printf( "Case #%d:\n%.2lf\n", ++cas, ans / 100.0 );}return 0; }</span>
m個(gè)理財(cái)用于更新都只有一次，所以復(fù)雜度并不高

一個(gè)可以優(yōu)化的地方是，由于理財(cái)只有2500個(gè)，所以能夠用于更新的點(diǎn)其實(shí)最多也就5000個(gè)，可以離散化一下，這樣 dp[i] 乘的系數(shù)不再是val[i]，而是相鄰兩個(gè)離散點(diǎn)之間的val[]和，用前綴和處理一下就好了，可以快幾百ms

總結(jié)

以上是生活随笔為你收集整理的HDU 4833 Best Financing 一脸费用流的dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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