https://www.acwing.com/problem/content/description/902/
思路对于从 [ 1 , n ] [1,n] [1,n]的每一个数我们能做的操作是选或者不选,并且我们在选的过程要从小到大,并且对于每一种数字我们可以选择无穷多个(但是在背包容量范围内,这里的话就是在n范围内),那么这就是一个完全背包计数问题的裸题了,因为状态只有选择或者不选那么不难发现状态转移方程为: f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i − 1 ] [ j − k ] f[i][j]=f[i-1][j] + f[i-1][j-k] f[i][j]=f[i−1][j]+f[i−1][j−k],这里的k表示我们当前枚举到哪个数字了,滚动数组优化后为: f [ j ] = f [ j ] + f [ j − i ] f[j] = f[j] + f[j-i] f[j]=f[j]+f[j−i],然后初始化的时候我们定义 f [ 0 ] = 1 f[0]=1 f[0]=1表示的是0这个数能选的方法有1种
代码#include
using namespace std;
#define ll long long
#define mod 1000000007
const int N = 1e3+10;
ll f[N],n;
int main()
{
cin>>n;
f[0] = 1;
for(ll i = 1;i
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?