题解 P1806 【跑步】

· · 题解

题解太少啦只有俩篇，所以虽然不是什么创新解法也让我通过把 (●'◡'●)

一、设计状态 状态转移嘛，每次只能跑得更多，所以上一次跑了几圈肯定是一个状态。然后要跑完n圈,所以一共跑了几圈也算一个状态，不然我们怎么知道跑完了没呢？？

定义dp[i][j]为总共跑了i圈最后一次跑j圈

二、状态转移

转移方程:dp[i][j]+=dp[i-j][q];

那么显然,当跑了i圈且这次跑j圈，上一次肯定跑q圈,q<j

初始化很显然,当总共跑i圈时这次跑i圈的方案是一种

for(int i=1;i<=n;i++)   dp[i][i]=1;

三重循环:

for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            for(int q=1;q<j;q++)
                dp[i][j]+=dp[i-j][q];

最后，由于题目要求不能1次跑完，所以不统计dp[i][i]

分割线

我们换一种思路.总共要跑n圈,每次可以跑1圈，2圈，....n圈，直到凑出n为止。那是不是相当于有n个物品,物品的重量为1到n,同时价值也是1到n,选那些物品能凑出n呢??这是一个简单的背包问题了。

值得一提的是,这是n^2的做法。