題意：小P去旅游，給你n個城市，m條路以及m條路的花費，還有一些特定的城市，這些城市必須經(jīng)過，并且到達這一城市還要先拿到證，在工作去掙錢；

問你是否能通過所有的特定城市。

題解：狀態(tài)方程：dp[i|(1<<k)][k] = max(dp[i|(1<<k)][k],dp[i][j] - d[num[k]][num[j]] - D[k]+C[k]);

表示到達第k個城市的的狀態(tài)的最多的錢

?

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int M = 1<<16; #define INF 2122219134 int dp[M+2][20]; int d[105][105]; int num[20],C[20],D[20]; int n; void Floyd(){for(int k = 1;k <= n;k++)for(int i = 1;i <= n;i++)for(int j = 1;j <= n;j++)if (d[i][k] < INF && d[k][j] < INF && d[i][j] > d[i][k]+d[k][j])d[i][j] = d[i][k] + d[k][j]; } int main(){int t,u,v,w;int m,money,H;cin >> t;while(t--){cin >> n >> m >> money;memset(d,126,sizeof(d)); // cout << d[0][0] << endl;for(int i = 1;i <= n;i++) d[i][i] = 0;for(int i = 0;i < m;i++){cin >> u >> v >> w;d[u][v] = d[v][u] = min(d[u][v],w);}Floyd();cin >> H;memset(dp,-1,sizeof(dp));for(int i = 0;i < H;i++){cin >> num[i] >> C[i] >> D[i];if(money > d[num[i]][1] + D[i])dp[1<<i][i] = max(dp[1<<i][i],money - d[num[i]][1] - D[i] + C[i]);}int cnt = (1<<H) - 1;for(int i = 0;i < cnt;i++){for(int j = 0;j < H;j++){if(!(i&(1<<j))) continue;for(int k = 0;k < H;k++){if(i&(1<<k)) continue;if(dp[i][j] >= d[num[j]][num[k]] + D[k])dp[i|(1<<k)][k] = max(dp[i|(1<<k)][k],dp[i][j] - d[num[j]][num[k]] - D[k] + C[k]);}}}int flag = 0;for(int i = 0;i < H;i++){if(dp[cnt][i] - d[num[i]][1] >= 0){flag = 1;break;}}if(flag) cout << "YES" << endl;else cout << "NO" << endl;} }

總結(jié)

以上是生活随笔為你收集整理的hdu -4284 Travel(状态压缩)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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