「LibreOJ NOIP Round #1」旅游路線

---

題目鏈接

做法：

首先肯定要預處理些東西，來使單詞詢問達到\(o(logn)\)或者\(o(1)\)的復雜度，又因為距離這個東西的范圍太大，我們考慮預處理一些費用相關的東西。

考慮\(dp[s][j]\)表示從s出發花費j元，走的最長的距離，如果求出了這個東西，顯然距離隨費用單調遞增，直接在\(dp[s]\)內二分即可。

可以列出方程：\(dp[s][j] = max(dp[t][j-p[s]]+dis[s][t])\), \(dis[s][t]\)表示從s到t，在s加一次油走到t最長經過的距離。

考慮如何計算\(dis[s][t]\)，用\(dis[s][t][C]\)表示從s到t用不超過C的油最長的距離，直接可以folyd求出答案，但是顯然會tle，于是可以采用倍增 floyd 的方法預處理數 \(dis[s][t][1,2,4,8...]\) 即預先計算 \(dis[s][t][k]\) 表示從 s 到 t 初始油量為 \(2^k\) 能走的最長距離，然后就可以對于每個起點，合并出它的答案。注意在預處理時不用考慮油量的限制。

深刻的感受到了要注意細節，這份時間爆炸的代碼換個頭文件都能tle。。。懇請知道原因的大佬賜教。

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) typedef long long ll; const int N = 110; const int inf = 0x3f3f3f3f; inline int read() {char c=getchar(); int x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } using namespace std; int n,m,C,T,p[N],c[N];int dis[17][N][N], dp[N][N*N]; void init_dis() {rep(s,1,16) {memcpy(dis[s],dis[s-1],sizeof(dis[s]));rep(k,1,n)rep(i,1,n)if(dis[s-1][i][k]!=-1)rep(j,1,n)if(dis[s-1][k][j]!=-1){dis[s][i][j]=max(dis[s][i][j],dis[s-1][i][k]+dis[s-1][k][j]);}} } int d[N][N],ans[N][N],tmp[17][N][N]; void getdis(int s) {memset(ans,-1,sizeof(ans));rep(i,1,n)ans[i][i]=0;memset(tmp,-1,sizeof(tmp));rep(x,0,16)if(min(c[s],C)&(1<<x)){rep(i,1,n)tmp[x][i][i] = 0;rep(k,1,n)rep(i,1,n)if(ans[i][k]!=-1)rep(j,1,n)if(dis[x][k][j]!=-1){tmp[x][i][j] = max(tmp[x][i][j],ans[i][k]+dis[x][k][j]);}rep(i,1,n)rep(j,1,n)ans[i][j]=tmp[x][i][j];}rep(i,1,n) d[s][i] = ans[s][i]; } void init() {init_dis();rep(i,1,n)getdis(i);rep(j,0,n*n)rep(s,1,n)rep(t,1,n)if(j>=p[s]&&d[s][t]!=-1){dp[s][j] = max(dp[s][j],dp[t][j-p[s]]+d[s][t]);} } int main() {n = read(), m =read(), C = read(), T=read();rep(i,1,n) p[i]=read(),c[i]=read();int x,y,l;memset(dis,-1,sizeof(dis));rep(i,1,n)rep(s,0,16)dis[s][i][i]=0;rep(i,1,m) x=read(),y=read(),dis[0][x][y]=read();init();while(T--) {int s,q,d;s=read(),q=read(),d=read();int cs = lower_bound(dp[s],dp[s]+1+n*n,d) - dp[s];if(dp[s][cs]>=d&&q>=cs&&cs<=n*n)printf("%d\n",q-cs);else puts("-1");}return 0; }

轉載于:https://www.cnblogs.com/RRRR-wys/p/9432047.html

總結

以上是生活随笔為你收集整理的「LibreOJ NOIP Round #1」旅游路线的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。