題意：要連出一個(gè)從1-L的過(guò)山車線，給出n段可選的建設(shè)方案。每段都有起始位置，終止位置，代價(jià)，和樂(lè)趣程度。要實(shí)現(xiàn)1-L的長(zhǎng)度中，相鄰兩端要首尾相連，總建設(shè)代價(jià)控制在B之內(nèi)，問(wèn)最多能獲得多少樂(lè)趣程度。

解題思路：這里有兩個(gè)限制條件，L和B,最開始的思維可能是dp[i][j][k]表示前i段，修的長(zhǎng)度為j，花費(fèi)為k的最大價(jià)值。但根據(jù)數(shù)據(jù)量，這樣肯定會(huì)超時(shí)。這里同樣有一個(gè)條件要仔細(xì)挖掘，相鄰兩端要首尾相連，所以對(duì)應(yīng)長(zhǎng)度為L(zhǎng)，肯定要有一個(gè)段它的其實(shí)位置等于L，這樣我們就可以把每一段的首地址用哈希存起來(lái)，到時(shí)候枚舉到L就直接從哈希里面拿出來(lái)，這樣就會(huì)少了枚舉所有段的一層循環(huán)。dp[i][j]表示修的長(zhǎng)度為i，花費(fèi)為j的最大價(jià)值。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int maxn = 10005; struct Node {int start,end,len,cost,fun; }roller[maxn]; struct HashNode {int id,next; }HNode[maxn]; int L,N,B,dp[1005][1005]; //dp[i][j]表示修建的長(zhǎng)度為i，花費(fèi)為j的最大值 int h[maxn],cnt;bool cmp(Node a,Node b) {if(a.start == b.start) return a.end < b.end;return a.start < b.start; }void add(int len,int id) {HNode[cnt].id = id, HNode[cnt].next = h[len];h[len] = cnt++; }int main() {while(scanf("%d%d%d",&L,&N,&B)!=EOF){memset(h,-1,sizeof(h));memset(dp,-1,sizeof(dp));for(int i = 1; i <= N; i++){scanf("%d%d%d%d",&roller[i].start,&roller[i].len,&roller[i].fun,&roller[i].cost);roller[i].end = roller[i].start + roller[i].len;}dp[0][0] = 0;for(int i = 1; i <= N; i++)add(roller[i].start,i); //加入哈希節(jié)點(diǎn)for(int i = 0; i <= L; i++)for(int j = 0; j <= B; j++){if(dp[i][j] == -1) continue;int t = h[i];while(t != -1){if(roller[HNode[t].id].cost + j <= B)dp[roller[HNode[t].id].end][j + roller[HNode[t].id].cost] = max(dp[roller[HNode[t].id].end][j+roller[HNode[t].id].cost],dp[i][j]+roller[HNode[t].id].fun);t = HNode[t].next;}}int ans = -1;for(int i = 0; i <= B; i++)ans = max(ans,dp[L][i]);printf("%d\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的poj 3257(哈希+二维dp)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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