「NOIP2012」开车旅行
题面描述:
小\(A\)与小\(B\)开车旅行,两个点的距离是两个点的高度的差的绝对值,若两个点的距离相同,则认为海拔低的要更近,小\(A\)以离他次近的点作为目的地,小Ｂ以离他最近的点作为目的地,小\(A\)与小\(B\)轮流开车,若行驶距离超过或没有目的地则停止旅行.
回答两个问题:
1.给定\(x\),求那个点出发会使\(A\)开车行驶的路程:\(B\)开车行驶的路程最小。
2.对于一个出发点与给定的\(x\),求\(A\)开车行驶的路程与\(B\)开车行驶的路程。
题解:
可以用\(set\)或链表求出小\(A\)与小\(B\)在每一个点到达的目的地,对于这两个问题,其实得到的都是以下模型:
一个点走\(n\)步的路程
可以利用倍增求\(lca\)的思想,令\(dp[i][k]\)表示\(i\)走\(2^k\)步后到达的目的地,\(f[i][k]\)表示到\(dp[i][k]\)所要的路程。
但是这道题要求两个人的行驶路程,我们就令\(f[i][k][0/1]\)表示第0/1个人所行驶的路程。
由于小Ａ与小Ｂ轮流开车,可以dp最开始是谁开车,令\(dp[i][k][0/1]\)表示第0/1个人最开始开车,所到达的目的地,\(f[i][k][0/1][0/1]\)表示第0/1个人最开始开车,第0/1个人所行驶的路程。
当\(k=1\)时:
\(dp[i][k][0]=dp[dp[i][k-1][0]][k-1][1]\)
\(f[i][k][0][0]=f[i][k-1][0][0]+f[dp[i][k-1][0]][1][0]=f[i][k-1][0][0]\)
\(f[i][k][0][1]=f[i][k-1][0][1]+f[dp[i][k-1][0]][1][1]=f[dp[i][k-1][0]][1][1]\)
\(dp[i][k][1],f[i][k][1][0],f[i][k][1][1]\)则同理.
当\(k!=1\)时:
\(dp[i][k][0]=dp[dp[i][k-1][0]][k-1][0]\)
\(f[i][k][0][0]=f[i][k-1][0][0]+f[dp[i][k-1][0]][k-1][0][0]\)
\(dp[i][k][1],f[i][k][1][0],f[i][k][1][1],f[i][k][0][1]\)则同理.
可以发现,第一个人\("B"\)在\(k>=1\)时不会对答案产生贡献,则这一些状态可以舍弃.
预处理完\(dp\)数组后可以类似\(lca\)的统计答案
标签：旅行,路程,NOIP2012,行驶,目的地,开车,dp From： https://www.cnblogs.com/zhouhuanyi/p/16983570.html