[NOIP2017]逛公园

论:考场上是如何智障的

题目(洛谷)

NOIP每年至少一道dp题,然后就考在这道题目上了.

……从这道题开始我就zz了.

看k的数据范围,50以内,嗯,可以做dp.

dp[i][k]表示当前在第i个点,超过i到n的最短距离dis[i]的长度k时的路线条数。

于是方程就很好写了,dp[u][k]+=dp[v][dis[u]+k-dis[v]-w]

初值:dp[1][0]=1。

整个记忆化搜索就行。

然后这个题是个有向图,而且还有环存在,所以我们考虑倒着推过去。

从n开始向1推着走,记录当前状态是否被更新,如果当前状态已访问过再去更新,则说明有0的环存在,输出-1;

注意最后还要来一次dfs(n,k+1),用以判断0环。

答案就是∑dfs(n,i),0<=i<=k。

来说说我是怎么zz的吧。

dp[i][k]我表示的是当前在第i点,超过dis[n]的长度为k的方案数。

GG.

发表评论