- 浏览: 21906 次
- 性别:
- 来自: 南京
最新评论
输入n,和k,问将n用1到k这k个数字进行拆分,有多少种拆分方法。例如:n=5,k=3 则有n=3+2, n=3+1+1, n=2+1+1+1, n=2+2+1, n=1+1+1+1+1这5种拆分方法。
这个题目是个比较明显的动态规划,如果想不到是背包问题,也可以写出状态转移方程如下。
用a[i][j]表示考虑到用数j进行拼接时数字i的拼接方法,可以得到状态转移方程如下:a[i][j]=a[i][j-1]+a[i-j][j-1]+a[i-2j][j-1]+a[i-3j][j-1]…+a[0][j-1]意思很明显,就将j-1状态可以到达a[i][j]的状态的数字相加。由于得到的结果可能相当大,已经超过了long long,所以应该用大数。但是若跑完所有数据,用大数会超过一秒,我们通过大数的程序可以达到,最大的数字为33位,那么,我们可以将两个long long的数字进行拼接,组成一个超过33位的数。这样增加了速度,这种比较慢的算法也可以不超时。
view sourceprint?01 #include <iostream>
02 #include<cstdio>
03 using namespace std;
04
05 long long a[1200][200]={0},b[1200][120]={0};
06
07 int main()
08 {
09 int i,j,n,m,k;
10 long long inf,x;
11 inf=1;
12 for(i=0;i<18;i++)
13 {
14 inf=inf*10;
15 }
16 cin>>n>>m;
17 for(i=1;i<=n;i++)
18 {
19 b[i][1]=0;
20 a[i][1]=1;
21 for(j=2;j<=m;j++)
22 {
23 if(j>i)
24 {
25 a[i][j]=a[i][j-1];
26 b[i][j]=b[i][j-1];
27 continue;
28 }
29 a[i][j]=a[i][j-1];
30 b[i][j]=b[i][j-1];
31 for(k=1;k*j<=i;k++)
32 {
33 if(i-j*k==0)
34 {
35 a[i][j]++;
36 b[i][j]+=a[i][j]/inf;
37 a[i][j]=a[i][j]%inf;
38 }
39 else {
40 b[i][j]+=b[i-j*k][j-1];
41 a[i][j]+=a[i-j*k][j-1];
42 b[i][j]+=a[i][j]/inf;
43 a[i][j]=a[i][j]%inf;
44 }
45 }
46 }
47 }
48 if(b[n][m]!=0)
49 {
50 cout<<b[n][m];
51 }
52 cout<<a[n][m]<<endl;
53 return 0;
54 }
其实这个题有更快的方法,看上面这个式子a[i][j]=a[i][j-1]+a[i-j][j-1]+a[i-2j][j-1]+a[i-3j][j-1]…+a[0][j-1]我们可以发现,其实可以转到a[i][j]的状态有两种,一种是a[i][j-1]就是不用j这个数字拼接i这个数字的方法数,另一种是a[i-j][j]就是用了j这个数字拼接的到i-j的方法数那么状态转移方程就可以写成a[i][j]=a[i][j-1]+a[i-j][j]不用加那么多项,就降低了一个数量级的复杂度,仍然利用上面处理大数的方法。
view sourceprint?01 #include <iostream>
02 #include <cstdio>
03 #include <cstring>
04 using namespace std;
05
06 long long a[1100][110],b[1100][110],inf;
07
08 int main(){
09 int n,k,i,j;
10 for(inf=1,i=0;i<18;i++) inf*=10;
11 memset(a,0,sizeof(a));
12 memset(b,0,sizeof(b));
13 scanf("%d%d",&n,&k);
14 for(i=0;i<=k;i++) a[0][i]=1;
15 for(i=1;i<=k;i++){
16 for(j=1;j<=n;j++){
17 if(j-i<0){
18 b[j][i]=b[j][i-1];
19 a[j][i]=a[j][i-1];
20 continue;
21 }
22 b[j][i]=b[j][i-1]+b[j-i][i]+(a[j][i-1]+a[j-i][i])/inf;
23 a[j][i]=(a[j][i-1]+a[j-i][i])%inf;
24 }
25 }
26 if(b[n][k]) printf("%I64d",b[n][k]);
27 printf("%I64d\n",a[n][k]);
28 return 0;
29 }
其实我们还可以在空间上进行优化,看这个式子a[i][j]=a[i][j-1]+a[i-j][j]我们发现,如果外层循环式j实际上是上一次j在i的值,加上这次j在i-j的值,那么可以只开一维数组,代码如下:
view sourceprint?01 #include <iostream>
02 #include <cstdio>
03 #include <cstring>
04 using namespace std;
05
06 long long a[1100],b[1100],inf;
07
08 int main(){
09 int n,k,i,j;
10 for(inf=1,i=0;i<18;i++) inf*=10;
11 scanf("%d%d",&n,&k);
12 memset(a,0,sizeof(a));
13 memset(b,0,sizeof(b));
14 a[0]=1;
15 for(i=1;i<=k;i++){
16 for(j=1;j<=n;j++){
17 if(j-i<0) continue;
18 b[j]=b[j]+b[j-i]+(a[j]+a[j-i])/inf;
19 a[j]=(a[j]+a[j-i])%inf;
20 }
21 }
22 if(b[n]) printf("%I64d",b[n]);
23 printf("%I64d\n",a[n]);
24 return 0;
25 }
这实际上是完全背包问题,只是状态转移方程形式有所不同,不过状态转移的方向是完全相同的。for(j=1;j<=k;j++) for(i=1;i<=n;i++) a[i]=a[i]+a[i-j],是这个题目的方法,由于i是从前往后的,那么a[i]前面的a[i-j]已经是已经考虑了j,而如果是for(j=1;j<=k;j++) for(i=n;i>=1;i--) a[i]=a[i]+a[i-j] ;i是从后往前的,那么a[i-j]是没考虑j的,正是一个只能用一次的情形。
此题目是单组测试数据,那么有两种情况,一种是题目没说清楚,实际上是多组(这种情况只能试),一种是真正的单组,但是测试数据的文件特别多。这种情况每个文件会单独跑一次数据,多个文件加起来的时间就是你做这个题用的时间。如果是多组数据,我们一般喜欢打表,但是对于真正的单组数据,打表则是下下策,因为每跑一次就打一遍所有的表,很浪费时间。所以只跑出输入数据需要的结果即可,对于这个题目的第一种解法,如果打表的话,就只能TLE,所以以后遇到真正的单组,一定要注意这个问题。
另外一个需要注意的是关于64位整数的,64位整数的申明可以有__int64和long long两种,编译器都支持,但是对于有些OJ只支持long long,输入输出上可以”%I64d”也可以”%lld”对于Mingw和CodeBlocks只能用%I64d但是,对于有些OJ则只能用%lld,所以比赛之前务必把这个搞清楚。当然,cin和cout就不用考虑这么多了,但是会相对慢些。
这个题目是个比较明显的动态规划,如果想不到是背包问题,也可以写出状态转移方程如下。
用a[i][j]表示考虑到用数j进行拼接时数字i的拼接方法,可以得到状态转移方程如下:a[i][j]=a[i][j-1]+a[i-j][j-1]+a[i-2j][j-1]+a[i-3j][j-1]…+a[0][j-1]意思很明显,就将j-1状态可以到达a[i][j]的状态的数字相加。由于得到的结果可能相当大,已经超过了long long,所以应该用大数。但是若跑完所有数据,用大数会超过一秒,我们通过大数的程序可以达到,最大的数字为33位,那么,我们可以将两个long long的数字进行拼接,组成一个超过33位的数。这样增加了速度,这种比较慢的算法也可以不超时。
view sourceprint?01 #include <iostream>
02 #include<cstdio>
03 using namespace std;
04
05 long long a[1200][200]={0},b[1200][120]={0};
06
07 int main()
08 {
09 int i,j,n,m,k;
10 long long inf,x;
11 inf=1;
12 for(i=0;i<18;i++)
13 {
14 inf=inf*10;
15 }
16 cin>>n>>m;
17 for(i=1;i<=n;i++)
18 {
19 b[i][1]=0;
20 a[i][1]=1;
21 for(j=2;j<=m;j++)
22 {
23 if(j>i)
24 {
25 a[i][j]=a[i][j-1];
26 b[i][j]=b[i][j-1];
27 continue;
28 }
29 a[i][j]=a[i][j-1];
30 b[i][j]=b[i][j-1];
31 for(k=1;k*j<=i;k++)
32 {
33 if(i-j*k==0)
34 {
35 a[i][j]++;
36 b[i][j]+=a[i][j]/inf;
37 a[i][j]=a[i][j]%inf;
38 }
39 else {
40 b[i][j]+=b[i-j*k][j-1];
41 a[i][j]+=a[i-j*k][j-1];
42 b[i][j]+=a[i][j]/inf;
43 a[i][j]=a[i][j]%inf;
44 }
45 }
46 }
47 }
48 if(b[n][m]!=0)
49 {
50 cout<<b[n][m];
51 }
52 cout<<a[n][m]<<endl;
53 return 0;
54 }
其实这个题有更快的方法,看上面这个式子a[i][j]=a[i][j-1]+a[i-j][j-1]+a[i-2j][j-1]+a[i-3j][j-1]…+a[0][j-1]我们可以发现,其实可以转到a[i][j]的状态有两种,一种是a[i][j-1]就是不用j这个数字拼接i这个数字的方法数,另一种是a[i-j][j]就是用了j这个数字拼接的到i-j的方法数那么状态转移方程就可以写成a[i][j]=a[i][j-1]+a[i-j][j]不用加那么多项,就降低了一个数量级的复杂度,仍然利用上面处理大数的方法。
view sourceprint?01 #include <iostream>
02 #include <cstdio>
03 #include <cstring>
04 using namespace std;
05
06 long long a[1100][110],b[1100][110],inf;
07
08 int main(){
09 int n,k,i,j;
10 for(inf=1,i=0;i<18;i++) inf*=10;
11 memset(a,0,sizeof(a));
12 memset(b,0,sizeof(b));
13 scanf("%d%d",&n,&k);
14 for(i=0;i<=k;i++) a[0][i]=1;
15 for(i=1;i<=k;i++){
16 for(j=1;j<=n;j++){
17 if(j-i<0){
18 b[j][i]=b[j][i-1];
19 a[j][i]=a[j][i-1];
20 continue;
21 }
22 b[j][i]=b[j][i-1]+b[j-i][i]+(a[j][i-1]+a[j-i][i])/inf;
23 a[j][i]=(a[j][i-1]+a[j-i][i])%inf;
24 }
25 }
26 if(b[n][k]) printf("%I64d",b[n][k]);
27 printf("%I64d\n",a[n][k]);
28 return 0;
29 }
其实我们还可以在空间上进行优化,看这个式子a[i][j]=a[i][j-1]+a[i-j][j]我们发现,如果外层循环式j实际上是上一次j在i的值,加上这次j在i-j的值,那么可以只开一维数组,代码如下:
view sourceprint?01 #include <iostream>
02 #include <cstdio>
03 #include <cstring>
04 using namespace std;
05
06 long long a[1100],b[1100],inf;
07
08 int main(){
09 int n,k,i,j;
10 for(inf=1,i=0;i<18;i++) inf*=10;
11 scanf("%d%d",&n,&k);
12 memset(a,0,sizeof(a));
13 memset(b,0,sizeof(b));
14 a[0]=1;
15 for(i=1;i<=k;i++){
16 for(j=1;j<=n;j++){
17 if(j-i<0) continue;
18 b[j]=b[j]+b[j-i]+(a[j]+a[j-i])/inf;
19 a[j]=(a[j]+a[j-i])%inf;
20 }
21 }
22 if(b[n]) printf("%I64d",b[n]);
23 printf("%I64d\n",a[n]);
24 return 0;
25 }
这实际上是完全背包问题,只是状态转移方程形式有所不同,不过状态转移的方向是完全相同的。for(j=1;j<=k;j++) for(i=1;i<=n;i++) a[i]=a[i]+a[i-j],是这个题目的方法,由于i是从前往后的,那么a[i]前面的a[i-j]已经是已经考虑了j,而如果是for(j=1;j<=k;j++) for(i=n;i>=1;i--) a[i]=a[i]+a[i-j] ;i是从后往前的,那么a[i-j]是没考虑j的,正是一个只能用一次的情形。
此题目是单组测试数据,那么有两种情况,一种是题目没说清楚,实际上是多组(这种情况只能试),一种是真正的单组,但是测试数据的文件特别多。这种情况每个文件会单独跑一次数据,多个文件加起来的时间就是你做这个题用的时间。如果是多组数据,我们一般喜欢打表,但是对于真正的单组数据,打表则是下下策,因为每跑一次就打一遍所有的表,很浪费时间。所以只跑出输入数据需要的结果即可,对于这个题目的第一种解法,如果打表的话,就只能TLE,所以以后遇到真正的单组,一定要注意这个问题。
另外一个需要注意的是关于64位整数的,64位整数的申明可以有__int64和long long两种,编译器都支持,但是对于有些OJ只支持long long,输入输出上可以”%I64d”也可以”%lld”对于Mingw和CodeBlocks只能用%I64d但是,对于有些OJ则只能用%lld,所以比赛之前务必把这个搞清楚。当然,cin和cout就不用考虑这么多了,但是会相对慢些。
发表评论
-
KMP快速字符串查找算法
2011-08-25 19:29 672在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
求解最大公约数问题
2011-08-25 19:27 698最大公因数,又称最大公约数。是指 [n(≧2)个自然数 a1, ... -
堆排序(Heap Sort)算法学习
2011-08-25 19:26 1086在程序设计相关领域, ... -
背包问题介绍与分析
2011-08-25 19:24 1032背包问题是在1978年由Merkel和Hellman提出的。它 ... -
求平方根sqrt()函数的底层算法效率问题
2011-08-25 19:23 1292我们平时经常会有一些数据运算的操作,需要调用sqrt,exp, ... -
面试中常见的一些算法问题
2011-08-25 19:22 699Problem 1 : Is it a loop ? ( ... -
各种排序算法的C++实现与性能比较
2011-08-25 19:21 926排序是计算机算法中非常重要的一项,而排序算法又有不少实现方法, ... -
背包问题之硬币找零问题
2011-08-25 19:19 1176设有6 种不同面值的硬 ... -
求能被1到20的数整除的最小正整数
2011-08-25 19:18 1374求能被1到20的数整除的最小正整数。最直觉的方法是求1到20这 ... -
买书折扣最优惠问题解法
2011-08-25 19:17 756题目:在节假日的时候 ... -
二叉树中的最近公共祖先问题
2011-08-25 19:16 1324题目:要求寻找二叉树中两个节点的最近的公共祖先,并将其返回。 ... -
判断一个整数是否是2的N次方
2011-08-25 19:04 1827题目:给定一个整数num,判断这个整数是否是2的N次方。比如, ... -
字符串逆序的算法汇总
2011-08-25 19:01 1061很早就准备写一个字符串系列的面试题,本来已经写好了,大概有十几 ... -
计算从1到N中1的出现次数
2011-08-25 18:59 602给定一个十进制整数N, ... -
KMP快速字符串查找算法
2011-08-25 18:57 967在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
快速排序的递归实现
2011-08-25 18:54 760快速排序是对冒泡排序的一种改进。它的基本思想是:通过一次排序将 ... -
数字1亿里面有多少个1呢
2011-08-25 18:52 745乍看这题真够唬人的,群里看到这个题目后争先恐后的说看法。最简单 ... -
最大子序列、最长公共子串、最长公共子序列
2011-08-25 18:33 794最大子序列 最大子序列是要找出由数组成的一维数组中和最大的连续 ... -
一道关于男女比例的面试题
2011-08-25 16:56 1042阿里巴巴的一道面试题:说澳大利亚的父母喜欢女孩,如果生出来的第 ...
相关推荐
一条野路子,避免多循环原题链接:343. 整数拆分解题思路本解法主要思路就是将当前数为N时的情况精简为:f(N-2) * 2 和 f(N-3) * 3谁大取谁为
除了基本的循环解法,还可以考虑更高级的算法,如动态规划。动态规划是一种将问题分解成子问题并存储中间结果以避免重复计算的技术。对于连续整数和问题,我们可以创建一个二维数组dp[i][j],表示是否可以将i拆分成...
根据给定的文件信息,我们可以理解到这是一...该程序利用了递归的思想和动态规划的技术,有效地解决了这个问题。通过对算法逻辑的详细解析,我们可以更深入地理解这种类型问题的解法,并为进一步的学习和研究提供参考。
- `DP.ppt` 可能是一个关于动态规划的PPT教程,涵盖了基本概念和常见问题的解法。 - `动态规划经典题1.rar` 和 `动态编程经典题2.rar` 包含了若干经典动态规划题目,可以用来练习和理解动态规划的运用。 - `动态...
动态规划是一种通过将复杂问题分解为子问题来解决的方法,它特别适合处理具有重叠子问题和最优子结构的优化问题。对于单调序列问题,我们可以创建两个数组dp升和dp降,分别用于存储前i个数字中非降序和非升序排列的...
2. **分解问题**:将原问题拆分为子问题。 3. **递归解子问题**:递归处理每个子问题。 4. **合并子问题的解**:将所有子问题的解整合,得到原问题的解。 **问题1:最大值问题的分治解法** 1. **问题分析**:将n个...
01背包问题是背包问题的基础,通过动态规划的方法可以有效地解决问题。通过对状态转移方程的理解和适当的优化措施,可以提高算法的效率和空间利用。 #### 二、完全背包问题 **2.1 题目** 完全背包问题是指每种...
动态规划的思想是将大问题拆分成小问题,通过解决小问题逐步构建到解决大问题。在此报告中,动态规划被用于计算背包在不超过背包容量C的情况下所能达到的最大价值。 3. **算法步骤**: - 初始化一个二维数组V,...
常见的模型有线性规划、整数规划、动态规划等。 5. 解决方法:一旦模型建立,就需要使用特定的算法来求解。对于线性规划问题,图解法(如单纯形法)是常用的解决手段;而对于更复杂的问题,可能需要用到计算机软件...
混合背包问题的解法是动态规划在实际应用中的一个经典例子,也是各种算法竞赛中常见的题目类型,特别是对于编程能力的考察,如NOIP(全国青少年信息学奥林匹克竞赛)和ACM国际大学生程序设计竞赛等。掌握混合背包...
例3和例4进一步探讨了含绝对值的不等式解法,涉及到不等式的同解变换和整数解的选取。例如,不等式4 |1 - 3x| 可以通过拆分为两个不等式来解决,分别对应绝对值内部的表达式为正和为负。解集的计算需要细致的步骤,...
动态规划是一种通过将复杂问题分解成简单子问题来求解的方法,特别适用于解决具有重叠子问题和最优子结构的问题。 **算法原理**: 1. **状态定义**:设 \(d[i][j]\) 表示将 \(i\) 个物品划分为 \(j\) 份的方法数。 ...
【动态规划-(经典)整数拆分-Ignatius and the Princess III22】:这是一个动态规划问题,要求将一个给定的正整数拆分为若干个正整数之和,满足特定条件,如每个数的因子不超过3。 【二分搜索-边界问题总结28】:...
4. **动态规划**:如背包问题、最长公共子序列、斐波那契数列、矩阵链乘法等,动态规划是一种将问题分解为子问题并存储中间结果的高效解法,适用于解决复杂度较高的优化问题。 5. **贪心算法**:贪心策略通常用于...
- 等差数列求和公式用于例8,将100×100-99×99等式拆分成平方差,再利用公式计算。 - 平方差公式在例9中可能被应用,将平方项组合成(a+b)(a-b)的形式。 7. **有借有还法**: 在某些情况下,可以先借用或借...
**解法概述**:与第3题类似,同样可以采用动态规划的方法。定义状态dp[i]表示分解i的方案数,转移方程为dp[j] += dp[i] * comb(j/i-1, j-i),其中comb(n, m)为组合数计算函数。 --- ### 5\. 马的遍历问题 **问题...
4. 代数问题,涉及合买物品的总价和个个人的资金情况,需要学生对整数的拆分以及逻辑推理有较深理解。 5. 组合问题,学生需要通过握手的次数来判断参赛人数,考察组合数学基础。 6. 等比数列增长问题,涉及指数增长...
在解决动态规划、图论和组合数学问题时,快速幂可以大大降低时间复杂度,提高算法效率。 4. **模运算**:在数论中,模运算对于处理大整数和解决同余方程至关重要。理解模运算的性质,如模线性同余方程的解法(扩展...
递归算法是一种在解决问题时将问题拆分成更小的、相同或相似问题的方法。在编程中,递归是一种常见的技术,指的是函数直接或间接地调用自身来解决问题。递归算法的关键在于它必须能够将问题规模缩小,并且有一个明确...