自动搬运

查看原文

来自洛谷，原作者为

	翼德天尊 2019-09-26 ~ 2024-03-03

搬运于2025-08-24 21:30:32，当前版本为作者最后更新于2020-03-20 21:05:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，让我们分析一下题意，提炼后如下：

1.次数 > 1；

2.V后一秒 > V前一秒；

3.跑n圈。

理清了思路，还有一个问题，用什么方法做这题？

1.DFS（深搜），炸时间，取消；

2.BFS（广搜），依旧炸时间，取消；

3.暴力，当然更不行；

于是，经过了漫长的思考， 我们决定——

出来吧，皮卡丘 DP动规！

什么是动规？

动规，全称动态规划
指动态地演变每一步，类似著名的斐波那契数列：
末路等于来路之和……
实现过程即为开一个足够的数组，然后模拟每一步，最终答案为数组的第n项。
时间复杂度：低

话不多说，上AC代码！

#include<bits/stdc++.h>//棒棒哒头文件
using namespace std;
long long n,ans[501]; //分别为总圈数n以及动规数组,动规数组的第i个下标表示前i圈的方案总数
int main(){
    scanf("%d",&n);//输入
    ans[0]=1;//第0项暂时设为1，保证数据来源（相当于借的）
    for (int i=1;i<=n;i++){//模拟前i圈
    	for (int j=n;j>=i;j--){//模拟前i圈中每一圈的演变过程
    		ans[j]+=ans[j-i];//第i圈是由它的前i圈（1~i)演变而来
		}
	}
    //DP结束
	cout<<ans[n]-1<<endl;//完美输出
    return 0;//习惯性 好习惯撒花
}

不知道你看懂了没有呢，你看这里也没发双击666，不如直接“以赞代6”吧！

谢谢诸位捧场啦！！！