邯郸手机网站开发价格,时装 wordpress,建设摩托车是杂牌吗,设计云平台「LibreOJ NOIP Round #1」旅游路线 题目链接 做法#xff1a; 首先肯定要预处理些东西#xff0c;来使单词询问达到\(o(logn)\)或者\(o(1)\)的复杂度#xff0c;又因为距离这个东西的范围太大#xff0c;我们考虑预处理一些费用相关的东西。考虑\(dp[s][j]\)表示从s出发花… 「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 ia;ib;i)
typedef long long ll;
const int N 110;
const int inf 0x3f3f3f3f;
inline int read() {char cgetchar(); int x0,f1;while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}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)(1x)){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(jp[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(), Tread();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) xread(),yread(),dis[0][x][y]read();init();while(T--) {int s,q,d;sread(),qread(),dread();int cs lower_bound(dp[s],dp[s]1n*n,d) - dp[s];if(dp[s][cs]dqcscsn*n)printf(%d\n,q-cs);else puts(-1);}return 0;
}转载于:https://www.cnblogs.com/RRRR-wys/p/9432047.html
