407b专题

CodeForces 407B Long Path

题意: 有n+1个格子  起点在1  每个格子有个前进1的门  前n个格子有个返回的门(返回前面某个格子)  奇数次走进一个格子就去走返回门  偶数次走前进门  问  走到n+1要走过几道门 思路: 一看就是DP to[i]表示第i个格子的返回门 go[i]表示离开第i个格子需要的步数 sum[i]表示离开前i个格子需要的步数 明显  go[i]=sum[i-1]-sum[to