wwt_001

题解

/ 注册

全部文章 / 题解（共2篇）

小A的最短路

题意：给你一棵树包含n个顶点，和n-1条边。在这棵树的基础上再加一条边。求树上两个顶点之间的距离。题解：其实有题意我们很容易想到要求两个顶点之间的LCA,从而间接求解两个顶点之间的最短距离。1.首先我们考虑不做缆车，那就是求dist(x,y)2.我们在考虑做缆车的情况，但是有分两种情况2.1从x走...

2020-08-06

0 598

涂色PAINT

题意：给你一串字符串，用尽量少的涂色次数达到目标。题解：该题本质是区间dp，设字符串为s.我们定义dp[i][j]为达到s[i,j]目标最少的涂色次数.当[i,j]长度为1时,dp[i][j]=1;当[i,j]长度为2时,dp[i][j]=(s[i]==s[j])?1:2;当[i,j]长度大于2时...

2020-07-31

0 642