太原谁想做网站,网站首页图,网站内页权重怎么查,wordpress 页面 按钮大家可能会想#xff1a;正整数拆分谁不会啊#xff0c;2年级就会了#xff0c;为啥要学啊
例题
正整数拆分有好几种#xff0c;这里我们列举两种讲。 关系
我们看着第一幅图#xff0c;头向左转90#xff0c;记住你看到的图#xff0c;再来看第二幅图#xff0c;你…大家可能会想正整数拆分谁不会啊2年级就会了为啥要学啊
例题
正整数拆分有好几种这里我们列举两种讲。 关系
我们看着第一幅图头向左转90°记住你看到的图再来看第二幅图你会惊奇的发现第一幅图向左转90°就变成了第二幅图因此我们做出来一道题就能推出另外一题。这种情况我们称之为Ferrers图
例2
我们先思考状态定义f[i][j]表示把i恰好分成j个正整数的方案数
后面考虑状态转移方程第一步先列表格。 我相信聪明的你们已经发现了规律f[9][4]1221i5那行f[8][3]121i5那行的前4个
后面我们用数学方法推导一下规律 因此得到状态转移方程f[i][j]f[i-j][1]f[i-j][2]……f[i-j][j]但是时间复杂度为O(n^3)。于是我们进行优化。
我们看到f[i-j][1]f[i-j][2]……f[i-j][j-1]f[i-1][j-1]为什么因为根据前面的状态转移方程f[i-1][j-1]等于f[i-j][1]f[i-j][2]……f[i-j][j-1]。最后我们的状态转移方程变为f[i][j]f[i-1][j-1]f[i-j][j]
最后给个代码
cinnm;
for(int i1;in;i) f[i][1]1;
for(int j2;jm;j)for(int ij;in;i)f[i][j]f[i-1][j-1]f[i-j][j];
coutf[n][n]endl;
变种
太戈编程习题
456. 数的划分
题目描述
将整数n分成k份且每份不能为空。任意两个方案不能相同(不考虑顺序)。 例如n7k3下面三种分法被认为是相同的。 1,1,5;1,5,1;5,1,1; 问有多少种不同的分法。
#include bits/stdc.h
using namespace std;
#define N 210
#define K 16
int n,k,f[N][K];
int main(){freopen(partition.in,r,stdin);freopen(partition.out,w,stdout);cinnk;for(int i1;in;i) f[i][1]1;for(int j2;jk;j)for(int ij;in;i)f[i][j]f[i-1][j-1]f[i-j][j];coutf[n][k]endl;return 0;
}
457. 训练计划
题目描述
要想成为编程高手必须独立编程n个小时。作为编程教练你希望为孩子们设计一套训练计划将n个小时拆分成若干天完成。已知每天最多安排不能超过k小时你的训练计划要求每天的训练量不能出现下降。请问一共有多少种训练方案 #include bits/stdc.h
using namespace std;
#define N 350
#define K 34
long long n,k,f[N][K];
int main(){freopen(training.in,r,stdin);freopen(training.out,w,stdout);cinnk;for(long long i1;in;i) f[i][1]1;for(long long j2;jk;j)for(long long ij;in;i)f[i][j]f[i-1][j-1]f[i-j][j];long long ans0;for(long long i1;ik;i)ansf[n][i];coutansendl;return 0;
} 希望大家可以点个赞、关个住谢谢o(*^^*)o
