首页 > 其他分享 >CF301B Yaroslav and Time 题解

CF301B Yaroslav and Time 题解

时间:2024-04-06 18:14:16浏览次数:24  
标签:right left int 题解 Yaroslav CF301B 105 dis

CF301B

这不最短路的板子题吗?

思路

用 \(ak\) 代表走到第 \(k\) 点时的可恢复单位时间的值。

\(i\) 到 \(j\) 的距离是 \(\left ( \left | xi-xj \right | + \left | yi-yj \right | \right ) \times d-ak\)。

再打一下最短路代码,建议 Floyd,因为短

AC Code

#include <bits/stdc++.h>
using namespace std;
int n,d,a[105],x[105],y[105],dis[105][105];
void floyd() {
	for(int k=1; k<=n; k++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				if(dis[i][j]>dis[i][k]+dis[k][j]&&j!=k&&i!=k)
					dis[i][j]=dis[i][k]+dis[k][j];
}
int main() {
	cin>>n>>d;
	for(int i=2; i<n; i++) cin>>a[i];
	for(int i=1; i<=n; i++) cin>>x[i]>>y[i];
	for(int i=1; i<=n; dis[i][i]=0,i++)
		for(int j=i+1; j<=n; j++)
			dis[i][j]=(abs(x[j]-x[i])+abs(y[j]-y[i]))*d-a[j],dis[j][i]=(abs(x[j]-x[i])+abs(y[j]-y[i]))*d-a[i];
	floyd();
	cout<<dis[1][n];
	return 0;
}

标签:right,left,int,题解,Yaroslav,CF301B,105,dis
From: https://www.cnblogs.com/AUBSwords/p/18117697

相关文章

  • CF30D King's Problem? 题解
    CF30D题意有\(n+1\)个点,其中的\(n\)个点在数轴上。求以点\(k\)为起点走过所有点的最短距离,允许重复。思路有两种情况:\(k\)在数轴上(如图1)。\(k\)在第\(n+1\)个点上(如图2)。图1:图2:像第一种情况:一定存在数轴上某点\(k\),使得人先走遍\(1\simk\),回来,再走遍......
  • CF1915B Not Quite Latin Square 题解
    CF1915B题意给出一个\(3\)行\(3\)列的字符矩形,其中每行都有字符ABC各一个组成,现有一个字符未知,求出未知字符。思路就是说每个字符都应该出现\(3\)次,所以我们只要找到出现两次的字符即可。ACCode#include<bits/stdc++.h>usingnamespacestd;intt;chara[10][10......
  • CF916C 题解
    CF916C题解思路思考发现,如果我们让很多边的边权变得非常大,而故意留下\(1\)到\(n\)的某一条路径,使整条路径之和甚至还没有剩下一条边的权值大,这条路径显然就是最短路了。更重要的是,这样构造的结果,这条路径同时还是整张图的最小生成树。这样我们只需要找一个\(100000\)......
  • P6680 [CCO2019] Marshmallow Molecules 题解
    P6680题意一个\(n\)点\(m\)边的图,图无重边,无自环。满足这样一条性质:如果三边互不相等,则三边可以构成三角形。思路思路简单,用集合的思想来做。引用一下K0stlin大佬的性质:题目中的操作等价于将一个点大于某个儿子的儿子们赋给这个儿子(这里的儿子表示这个点有出边连向的......
  • CF1883B Chemistry 题解
    原题传送门思路:如"aba","abba"这样的回文字符串,每个字符的出现次数有以下两种情况:1:全部是偶数(abba)2:只有一个为奇数(aba)于是只要字符出现个数为奇数的个数小于等于k+1即可否则无解ACcode:#include<bits/stdc++.h>usingnamespacestd;intt,n,k,number[50];strings;......
  • CF895C Square Subsets 题解
    看到\(a_i\le70\)后,发现\(n\)啥用没有,因为只需要枚举\(1-70\)选几个即可。看到求完全平方数后,想到分解质因数,由于\(a_i\le70\),所以只有\(19\)个质数,可以进行状压dp。设\(dp_{i,j}\)表示枚举到\(i\),状态为\(j\)的方案数,便有:\[dp_{i,j}=dp_{i-1,j}+dp_{i-1,j\o......
  • 题解:AT_xmascon21_b Bad Mood
    AT_xmascon21_bBadMood题意给定你一个\(n\timesm\)的矩形。以一条对角线为基础上,制作一个无向图,该图的顶点对应于格子的共有\((m+1)\times(n+1)\)个顶点,画上的对角线对应于图的边。这种方式能形成的连通分量的数量为得分。求最小得分和最大得分。思路最小得分是好......
  • 题解:CF1918B Minimize Inversions
    CF1918BMinimizeInversions思路暴力一个一个的算,复杂度巨大。数学规律让逆序最少,也就是让升序更多。我们可以通过多组数据实验,最终我们会发现,将数列\(A\)减少一个逆序对,让数列\(B\)随着\(A\)变化,最多会只会增加一个逆序对。而让\(A\)相邻两个数保持升序,\(B\)相邻......
  • CF1934B Yet Another Coin Problem 题解
    CF1934BYetAnotherCoinProblem题解题意目前有\(5\)种硬币,面值分别为\(1,3,6,10,15\)。给你一个数字\(n\),求出可以凑出\(n\)的最少的硬币的数量。思路这道题,大多数的人大概会想到动态规划的方法。但是,我们应该有敢于创新的精神。于是我就想到了一个简单的数学方法......
  • CF1950B Upscaling题解
    CF1950BUpscaling题解题意给予你一个正整数\(n\),构造一个如图的字符矩阵。思路注意数据\(1\len\le20\),可以发现数据很小,于是我们可以暴力模拟。我们可以将两列看为一列,两行看为一行。然而我们可以发现缩成的一行的\(i\)等于被缩的两行的\({i\div2}\)的向上取整。......