題意：
? ? ? 給你一個(gè)有向圖，每個(gè)節(jié)點(diǎn)上都有一個(gè)鹽價(jià)，然后給你k個(gè)空間，么個(gè)空間上節(jié)點(diǎn)與節(jié)點(diǎn)的距離不變，但鹽價(jià)不同，對于每一個(gè)節(jié)點(diǎn)，有三種操作，賣一袋鹽，買一袋鹽 ,不交易，每一個(gè)節(jié)點(diǎn)可以跳掉（當(dāng)前空間+1）%K的空間（特別注意，起點(diǎn)1和終點(diǎn)n不可以穿越），花費(fèi)是時(shí)間1，金錢0 ，節(jié)點(diǎn)與節(jié)點(diǎn)之間都有花費(fèi)時(shí)間和花費(fèi)金錢，過程中金錢不可以是負(fù)數(shù)，問從節(jié)點(diǎn)1出發(fā)，在限制的時(shí)間內(nèi)到達(dá)節(jié)點(diǎn)n的最大金錢數(shù)。


思路：

? ? ?這個(gè)題目做了將近兩天，一開始寫了各種深搜，各種超時(shí)，各種wa然后就開始各種廣搜，寫了很多版本，終于有一個(gè)能過的了，這個(gè)題目關(guān)鍵是就超時(shí)問題，說下思路，首先我們可以開一個(gè)數(shù)組mark[i][t][k][b] 表示的是第i個(gè)節(jié)點(diǎn)第t時(shí)刻，在第k層，有b袋鹽的最大金錢數(shù)，然后就是搜索，寫完了就是各種超時(shí)？為什么會超時(shí)，是因?yàn)槲覀冞M(jìn)隊(duì)出隊(duì)次數(shù)太多，如果隨意一算可能會這么想 可能會如認(rèn)為進(jìn)隊(duì)次數(shù)是 N * T * K * B也就是mark的最大組合數(shù)，其實(shí)不然，對于同一個(gè)狀態(tài)可能會進(jìn)隊(duì)多次，如果我們什么也不管，直接暴力，就是能更新就更新然后進(jìn)隊(duì)列，那么就會出現(xiàn)這么一種情況“當(dāng)前這一步比之前的大了，我們直接更新進(jìn)隊(duì)，過了一會之后又來了一個(gè)，更新后的更大了，那么我們在更新進(jìn)入隊(duì)列”不要小看這兩次進(jìn)隊(duì)，其實(shí)第一次進(jìn)隊(duì)我們所付出的代價(jià)是什么，代價(jià)是進(jìn)隊(duì)后更新后面的可更新的，等第二次進(jìn)隊(duì)了，再把后面的能更新的又更新了，這樣的話，暴搜的代價(jià)就很大了，具體多大我算不明白，但妥妥保證你超時(shí)，就算你之前寫一個(gè)逆向的最短路作為優(yōu)化，照樣超時(shí)（我試過很多種），那么該怎么辦呢？其實(shí)對于每一個(gè)點(diǎn)，我們可以先把他的最優(yōu)求出來，然后再去更新別人，因?yàn)槭亲顑?yōu)，所以這個(gè)點(diǎn)只會進(jìn)隊(duì)列一次，那怎么求最優(yōu)呢？我們可以開個(gè)優(yōu)先隊(duì)列，就是把廣搜的隊(duì)列用優(yōu)先隊(duì)列，每次取出時(shí)間最小的，這樣對于當(dāng)前時(shí)間，比如是4，那么5這個(gè)時(shí)間點(diǎn)更新的時(shí)候<=4的肯定更新到最優(yōu)了，所以這樣每個(gè)點(diǎn)只要進(jìn)隊(duì)列一次就行了，優(yōu)化了時(shí)間就可以ac了，如果你不滿足于ac，還想更快，可以在寫一個(gè)最短路去優(yōu)化，反向存邊，時(shí)間是權(quán)值，從終點(diǎn)跑一遍最短路，然后對于每一步來說，如果時(shí)間已經(jīng)不能到終點(diǎn)了，那么當(dāng)前終點(diǎn)就直接continue了。

#include<stdio.h> #include<string.h> #include<queue>#define N_node 110 #define N_edge 220 #define INF 1000000000 using namespace std;typedef struct {int to ,next ,time ,money; }STAR;typedef struct NODE {int nowt ,nowc ,nowy ,id;friend bool operator < (NODE a ,NODE b){return a.nowt < b.nowt;} }NODE;STAR E[N_edge]; NODE xin ,tou; int list[N_node] ,tot; int pic[6][N_node]; int mark[N_node][220][8][8]; int mk[N_node][220][8][8]; int N ,M ,B ,K ,R ,T ,Ans;void add(int a ,int b ,int c ,int d) {E[++tot].to = b;E[tot].time = c;E[tot].money = d;E[tot].next = list[a];list[a] = tot; }void BFS() {memset(mark ,255 ,sizeof(mark));memset(mk ,0 ,sizeof(mk));xin.id = 1 ,xin.nowc = 0 ,xin.nowt = T ,xin.nowy = 0;priority_queue<NODE>q;q.push(xin);mark[xin.id][xin.nowt][xin.nowc][xin.nowy] = R;mk[xin.id][xin.nowt][xin.nowc][xin.nowy] = 1;while(!q.empty()){tou = q.top();q.pop(); if(tou.id == N){if(Ans < mark[tou.id][tou.nowt][tou.nowc][tou.nowy])Ans = mark[tou.id][tou.nowt][tou.nowc][tou.nowy];continue;}for(int k = list[tou.id] ; k ;k = E[k].next){xin.id = E[k].to;xin.nowc = tou.nowc;xin.nowt = tou.nowt - E[k].time;int cost = mark[tou.id][tou.nowt][tou.nowc][tou.nowy] - E[k].money;if(xin.nowt < 0 || cost < 0) continue;if(xin.id == 1 && xin.nowc || xin.id == N && xin.nowc)continue;//不交易 xin.nowy = tou.nowy;if(cost > mark[xin.id][xin.nowt][xin.nowc][xin.nowy]){mark[xin.id][xin.nowt][xin.nowc][xin.nowy] = cost;if(!mk[xin.id][xin.nowt][xin.nowc][xin.nowy]) {mk[xin.id][xin.nowt][xin.nowc][xin.nowy] = 1;q.push(xin);}}if(xin.id == 1 || xin.id == N) continue;//買 xin.nowy = tou.nowy + 1;if(xin.nowy <= B && cost - pic[xin.nowc][xin.id] >= 0){if(cost - pic[xin.nowc][xin.id] > mark[xin.id][xin.nowt][xin.nowc][xin.nowy]){mark[xin.id][xin.nowt][xin.nowc][xin.nowy] = cost - pic[xin.nowc][xin.id];if(!mk[xin.id][xin.nowt][xin.nowc][xin.nowy]){mk[xin.id][xin.nowt][xin.nowc][xin.nowy] = 1;q.push(xin);}}} //賣 xin.nowy = tou.nowy - 1;if(xin.nowy >= 0){if(cost + pic[xin.nowc][xin.id] > mark[xin.id][xin.nowt][xin.nowc][xin.nowy]){mark[xin.id][xin.nowt][xin.nowc][xin.nowy] = cost + pic[xin.nowc][xin.id];if(!mk[xin.id][xin.nowt][xin.nowc][xin.nowy]){mk[xin.id][xin.nowt][xin.nowc][xin.nowy] = 1;q.push(xin);}}} }if(tou.id == 1 || tou.id == N) continue;xin.id = tou.id;xin.nowc = (tou.nowc + 1) % K;xin.nowt = tou.nowt - 1;if(xin.nowt < 0) continue;int cost = mark[tou.id][tou.nowt][tou.nowc][tou.nowy];//不交易 xin.nowy = tou.nowy;if(cost > mark[xin.id][xin.nowt][xin.nowc][xin.nowy]){mark[xin.id][xin.nowt][xin.nowc][xin.nowy] = cost;if(!mk[xin.id][xin.nowt][xin.nowc][xin.nowy]) {mk[xin.id][xin.nowt][xin.nowc][xin.nowy] = 1;q.push(xin);}}//買 xin.nowy = tou.nowy + 1;if(xin.nowy <= B && cost - pic[xin.nowc][xin.id] >= 0){if(cost - pic[xin.nowc][xin.id] > mark[xin.id][xin.nowt][xin.nowc][xin.nowy]){mark[xin.id][xin.nowt][xin.nowc][xin.nowy] = cost - pic[xin.nowc][xin.id];if(!mk[xin.id][xin.nowt][xin.nowc][xin.nowy]){mk[xin.id][xin.nowt][xin.nowc][xin.nowy] = 1;q.push(xin);}}} //賣 xin.nowy = tou.nowy - 1;if(xin.nowy >= 0){if(cost + pic[xin.nowc][xin.id] > mark[xin.id][xin.nowt][xin.nowc][xin.nowy]){mark[xin.id][xin.nowt][xin.nowc][xin.nowy] = cost + pic[xin.nowc][xin.id];if(!mk[xin.id][xin.nowt][xin.nowc][xin.nowy]){mk[xin.id][xin.nowt][xin.nowc][xin.nowy] = 1;q.push(xin);}}} } }int main () {int i ,j ,a ,b ,c ,d;int cas = 1 ,t;scanf("%d" ,&t);while(t--){scanf("%d %d %d %d %d %d" ,&N ,&M ,&B ,&K ,&R ,&T);for(i = 0 ;i < K ;i ++)for(j = 1 ;j <= N ;j ++)scanf("%d" ,&pic[i][j]);memset(list ,0 ,sizeof(list)) ,tot = 1;for(i = 1 ;i <= M ;i ++){scanf("%d %d %d %d" ,&a ,&b ,&c ,&d);add(a ,b ,c ,d);}Ans = -1;BFS();printf("Case #%d: " ,cas ++);Ans == -1 ? puts("Forever Alone"):printf("%d\n" ,Ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu4784 不错的搜索（ 买卖盐，要求整钱最多）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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