1 条题解
-
0
前置知识:状压 dp
首先,因为只能沿路程最短的路径行驶,且只能在交叉口改变速度,不难想到 dp。
令 表示在位置 ,已经行驶了 分钟耗油的最小值,令速度的取值为 ,不难得出转移方程:
$dp[i][j][k] = \min(dp[i - 1][j][k - l/speed],dp[i][j-1][k-l/speed])$
当然这只是从左下到右上的情况。剩下的情况相信读者可以自己推出。
那么现在有一个问题:上式中 未必是一个整数,例如以 英里每小时的速度经过长度为 英里的道路,所需的时间就是 分钟。
看一眼数据范围,发现速度仅有 种不同的取值,并且分别是 的倍数。
当速度为 英里每小时时,行驶一英里所需要的时间为 分钟。
速度为 英里每小时时,行驶一英里所需时间为 分钟。
同理,接下来依次为 分钟。
所以我们将耗时乘上 ,那么每次用时必定为整数,就可以进行 dp 了。
时间复杂度 ,但由于常数足足有 倍大(枚举速度还要乘上 ),所以炸时间也炸空间。
考虑进行优化。
优化 1:
一个小优化。
观察到用时的分钟数都是 的形式,而为了使用时为整数,我们只需使分母是 的倍数即可。
,故只需将耗时乘上 即可。
于是我们成功地将常数减小至 。
但仍不能满足本题的数据范围 。
故考虑优化 2 。
优化 2:
本题的关键优化。
显然,在将耗时乘上 之后,不是所有耗时都能被取到。
这一点比较难理解,就拿样例来举个例子吧。
样例 1 中,每段路的长度为 英里,而速度的取值仅有 种,而这 种速度通过一段路的时间乘上 后分别为: $50400,25200,16800,12600,10080,8400,7200,6300,5600,5040$
在 dp 的转移过程中,显然取时间为 中的任意一个时,这个转移都是无效的。因为这些时间不可能被上面的所有可能的耗时组合而成。
类似这样的时间点还有很多,关键在于如何找到这些时间点并预先排除。
考虑使用分组背包。先将所有可能的时间值储存在一个数组里(如样例 1 即为 $\{50400,25200,16800,12600,10080,8400,7200,6300,5600,5040\}$ )
且最多经过 条道路。
所以我们假设有 个分组,每组有 种物品,对应上述的数组,最后统计哪些数出现过,在 dp 时仅需考虑这些状态中小于等于 的状态就行了。
在极限情况下(),经过测试,情况数不超过 。
设情况数为 ,则时间复杂度为 ,常数仅有枚举速度的 ,足以通过本题。
主体部分完成,输出前统计有效状态即可。
完整代码(码风可能有点神奇,不喜勿喷):
#include <cstdio> #include <cstring> #include <algorithm> int n,l,z,x1,x2,y1,y2,t1,t2,cnt,row,column,time1,time2,possible[15],limit_row[20],limit_column[20],states[30010],map[2100010],road_row[15][15],road_column[15][15]; double waste1,waste2,dp[15][15][30010]; bool vis[2110010]={true}; int abs(int x){ return x>0?x:(-x); } template<typename T>T min(T x,T y){ return x<y?x:y; } int ceil(double x){ if((int)x==x)return x; else return (int)x+1; } double cost(int speed){ return (double)l/210/(80-0.03*speed*speed); } int main(){ scanf("%d %d",&n,&l);l*=210; for(register int i=1;i<=n;i++)scanf("%d",&limit_row[i]); for(register int i=1;i<=n;i++)scanf("%d",&limit_column[i]); scanf("%d %d %d %d %d %d",&x1,&y1,&x2,&y2,&t1,&t2); row=abs(y2-y1)+1,column=abs(x2-x1)+1,t1*=210,t2*=210; z=x1,x1=y1,y1=z,z=x2,x2=y2,y2=z; for(register int i=1;i<=10;i++)possible[i]=12*l/i; for(register int i=1;i<=2*(n-1);i++)for(register int j=t2;j>=0;j--)for(register int k=1;k<=10;k++)vis[j+possible[k]]|=vis[j]; for(register int i=0;i<=t2;i++)if(vis[i])states[++cnt]=i,map[i]=cnt; if(x1>x2&&y1>y2)for(register int i=x1;i>=x2;i--)for(register int j=y1;j>=y2;j--)road_row[x1-i+1][y1-j+1]=limit_row[i],road_column[x1-i+1][y1-j+1]=limit_column[j]; if(x1<=x2&&y1>y2)for(register int i=x1;i<=x2;i++)for(register int j=y1;j>=y2;j--)road_row[i-x1+1][y1-j+1]=limit_row[i],road_column[i-x1+1][y1-j+1]=limit_column[j]; if(x1>x2&&y1<=y2)for(register int i=x1;i>=x2;i--)for(register int j=y1;j<=y2;j++)road_row[x1-i+1][j-y1+1]=limit_row[i],road_column[x1-i+1][j-y1+1]=limit_column[j]; if(x1<=x2&&y1<=y2)for(register int i=x1;i<=x2;i++)for(register int j=y1;j<=y2;j++)road_row[i-x1+1][j-y1+1]=limit_row[i],road_column[i-x1+1][j-y1+1]=limit_column[j]; for(register int i=1;i<=row;i++)for(register int j=1;j<=column;j++)for(register int k=1;k<=cnt;k++)dp[i][j][k]=1e9;dp[1][1][1]=0; for(register int i=1;i<=row;i++){ for(register int j=1;j<=column;j++){ for(register int k=1;k<=cnt;k++){ for(register int p=1;p<=10;p++){ if(l*12/p<=states[k]&&map[states[k]-l*12/p]){ double waste=1e9; if(i!=1&&road_column[i-1][j]>=p*5)waste=min(waste,dp[i-1][j][map[states[k]-l*12/p]]+cost(p*5)); if(j!=1&&road_row[i][j-1]>=p*5)waste=min(waste,dp[i][j-1][map[states[k]-l*12/p]]+cost(p*5)); dp[i][j][k]=min(dp[i][j][k],waste); } } } } } time1=1e9,waste1=1e9,time2=1e9,waste2=1e9; for(register int i=1;i<=cnt;i++){ if((dp[row][column][i]||(row==1&&column==1&&i==1))&&dp[row][column][i]!=1e9&&states[i]>=t1&&states[i]<=t2){ if(states[i]<=time1){ if(states[i]<time1)waste2=dp[row][column][i]; else waste2=min(waste2,dp[row][column][i]); time1=states[i]; } if(dp[row][column][i]<=waste1){ if(dp[row][column][i]<waste1)time2=states[i]; else time2=min(time2,states[i]); waste1=dp[row][column][i]; } } } if(time1==1e9||waste1==1e9)printf("No"); else printf("%d %.2lf\n%d %.2lf",(int)ceil(time1/210.0),waste2,(int)ceil(time2/210.0),waste1); return 0; }upd 2022.7.14 原来的程序忘删调试语句了...
- 1
信息
- ID
- 2728
- 时间
- 2000ms
- 内存
- 125MiB
- 难度
- 9
- 标签
- 递交数
- 19
- 已通过
- 4
- 上传者