1 条题解

  • 0
    @ 2026-5-10 3:11:04

    前置知识:状压 dp

    首先,因为只能沿路程最短的路径行驶,且只能在交叉口改变速度,不难想到 dp。

    dp[i][j][k]dp[i][j][k] 表示在位置 (i,j)(i,j),已经行驶了 kk 分钟耗油的最小值,令速度的取值为 speedspeed,不难得出转移方程:

    $dp[i][j][k] = \min(dp[i - 1][j][k - l/speed],dp[i][j-1][k-l/speed])$

    当然这只是从左下到右上的情况。剩下的情况相信读者可以自己推出。

    那么现在有一个问题:上式中 kk 未必是一个整数,例如以 3535 英里每小时的速度经过长度为 1010 英里的道路,所需的时间就是 1207\dfrac{120}{7} 分钟。

    看一眼数据范围,发现速度仅有 1010 种不同的取值,并且分别是 1,2,3...,101,2,3...,10 的倍数。

    当速度为 55 英里每小时时,行驶一英里所需要的时间为 1÷5×60=1211 \div 5 \times 60 = \dfrac{12}{1} 分钟。

    速度为 1010 英里每小时时,行驶一英里所需时间为 122\dfrac{12}{2} 分钟。

    同理,接下来依次为 123,124,...,1210\dfrac{12}{3},\dfrac{12}{4},...,\dfrac{12}{10} 分钟。

    所以我们将耗时乘上 lcm(1,2,...,10)=2520\operatorname{lcm}(1,2,...,10)=2520,那么每次用时必定为整数,就可以进行 dp 了。

    时间复杂度 O(t2n2)O(t_2n^2),但由于常数足足有 2520025200 倍大(枚举速度还要乘上 1010),所以炸时间也炸空间。

    考虑进行优化。


    优化 1:

    一个小优化。

    观察到用时的分钟数都是 12x\dfrac{12}{x} 的形式,而为了使用时为整数,我们只需使分母是 lcm(1,2,...,10)\operatorname{lcm}(1,2,...,10) 的倍数即可。

    2520=12×2102520 = 12 \times 210故只需将耗时乘上 210210 即可。

    于是我们成功地将常数减小至 21002100

    但仍不能满足本题的数据范围 n10,t21000n \leq 10 , t_2 \leq 1000

    故考虑优化 2 。


    优化 2:

    本题的关键优化。

    显然,在将耗时乘上 210210 之后,不是所有耗时都能被取到。

    这一点比较难理解,就拿样例来举个例子吧。

    样例 1 中,每段路的长度为 2020 英里,而速度的取值仅有 1010 种,而这 1010 种速度通过一段路的时间乘上 210210 后分别为: $50400,25200,16800,12600,10080,8400,7200,6300,5600,5040$

    在 dp 的转移过程中,显然取时间为 150391-5039 中的任意一个时,这个转移都是无效的。因为这些时间不可能被上面的所有可能的耗时组合而成。

    类似这样的时间点还有很多,关键在于如何找到这些时间点并预先排除。

    考虑使用分组背包。先将所有可能的时间值储存在一个数组里(如样例 1 即为 $\{50400,25200,16800,12600,10080,8400,7200,6300,5600,5040\}$ )

    且最多经过 2×(n1)2 \times (n - 1) 条道路。

    所以我们假设有 2×(n1)2 \times (n - 1) 个分组,每组有 1010 种物品,对应上述的数组,最后统计哪些数出现过,在 dp 时仅需考虑这些状态中小于等于 t2t_2 的状态就行了。

    在极限情况下(n=10,t2=1000,l=1n = 10 , t_2 = 1000 , l = 1),经过测试,情况数不超过 3000030000

    设情况数为 cntcnt,则时间复杂度为 O(n2cnt)O(n^2cnt),常数仅有枚举速度的 1010,足以通过本题。


    主体部分完成,输出前统计有效状态即可。

    完整代码(码风可能有点神奇,不喜勿喷):

    #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
    上传者