这道题是给你一个有向图， 一个人从图中定点1走到定点N, 在除过1和N的顶点可以进行盐贸易， 他在一个定点每次可以卖出一包盐， 买一包盐， 不买不卖盐， 此外他有一个装置使用这个装置可以使自己瞬间穿送到另外一个宇宙的当前位置， 但是使用这个装置之前应该等待一分钟， 问他到达N点最多带多少钱 . 我们定义dp[T][k][N][b]为在T时刻k宇宙的N定点所能得到的钱数的最大值， 然后采用刷表法更新答案即可， 代码如下：
#include <cstdio> #include <algorithm> #include <cstring> #include <vector> using namespace std; int N, M, B, K, R, T; int price[10][150]; struct edge { int v, ct, cm; }; vector<edge> G[120]; int dp[205][10][110][10]; int main() { int TT; scanf("%d", &TT); int kase = 0; while(TT--) { scanf("%d%d%d%d%d%d", &N, &M, &B, &K, &R, &T); for(int i=0; i<K; i++) for(int j=1; j<=N; j++) scanf("%d", &price[i][j]); for(int i=0; i<=N; i++) G[i].clear(); for(int i=0; i<M; i++) { int x, y, t, m; scanf("%d%d%d%d", &x, &y, &t, &m); G[x].push_back((edge){y, t, m}); } memset(dp, -1, sizeof(dp)); dp[0][0][1][0] = R; int res = -1; for(int t=0; t<=T; t++) for(int k=0; k<K; k++) for(int u=1; u<=N; u++) for(int b=0; b<=B; b++) if(dp[t][k][u][b] >= 0) { if(u==N && k==0) continue; //res = max(res, dp[t][0][N][b]); for(int i=0; i<G[u].size(); i++) { edge e = G[u][i]; int v = e.v, ct = e.ct, cm = e.cm; if(k!=0 && (v==1 || v==N)) continue; //买一袋 if(t+ct<=T && b+1<=B && price[k][v]!=-1) dp[t+ct][k][v][b+1] = max(dp[t+ct][k][v][b+1], dp[t][k][u][b]-cm-price[k][v]); //什么都不干 if(t+ct<=T) dp[t+ct][k][v][b] = max(dp[t+ct][k][v][b], dp[t][k][u][b]-cm); //卖一袋 if(t+ct<=T && b-1>=0 && price[k][v]!=-1) dp[t+ct][k][v][b-1] = max(dp[t+ct][k][v][b-1], dp[t][k][u][b]-cm+price[k][v]); } int k1 = (k+1)%K; //穿越 if((u==1 || u==N) && k!=0) continue; //买一袋 if(t+1<=T && b+1<=B && price[k1][u]!=-1) dp[t+1][k1][u][b+1] = max(dp[t+1][k1][u][b+1], dp[t][k][u][b]-price[k1][u]); //什么也不买 if(t+1<=T) dp[t+1][k1][u][b] = max(dp[t+1][k1][u][b], dp[t][k][u][b]); //卖一袋 if(t+1<=T && b-1>=0 && price[k1][u]!=-1) dp[t+1][k1][u][b-1] = max(dp[t+1][k1][u][b-1], dp[t][k][u][b]+price[k1][u]); } for(int t=0; t<=T; t++) for(int b=0; b<=B; b++) res = max(res, dp[t][0][N][b]); if(res == -1) printf("Case #%d: Forever Alone ", ++kase); else printf("Case #%d: %d ", ++kase, res); } return 0; }