整数拆分的动态规划解法

其实也可以用背包来解决
服务器君一共花费了239.507 ms进行了4次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

输入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位的数。这样增加了速度,这种比较慢的算法也可以不超时。

#include <iostream>
#include<cstdio>
using namespace std;
long long a[1200][200]={0},b[1200][120]={0};
int main()
{
    int i,j,n,m,k;
    long long inf,x;
    inf=1;
    for(i=0;i<18;i++)
    {
        inf=inf*10;
    }
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        b[i][1]=0;
        a[i][1]=1;
        for(j=2;j<=m;j++)
        {
            if(j>i)
            {
                a[i][j]=a[i][j-1];
                b[i][j]=b[i][j-1];
                continue;
            }
            a[i][j]=a[i][j-1];
            b[i][j]=b[i][j-1];
            for(k=1;k*j<=i;k++)
            {
                if(i-j*k==0)
                {
                    a[i][j]++;
                    b[i][j]+=a[i][j]/inf;
                    a[i][j]=a[i][j]%inf;
                }
                else {
                    b[i][j]+=b[i-j*k][j-1];
                    a[i][j]+=a[i-j*k][j-1];
                    b[i][j]+=a[i][j]/inf;
                    a[i][j]=a[i][j]%inf;
                }
            }
        }
    }
    if(b[n][m]!=0)
    {
        cout<<b[n][m];
    }
    cout<<a[n][m]<<endl;
    return 0;
}

其实这个题有更快的方法,看上面这个式子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]不用加那么多项,就降低了一个数量级的复杂度,仍然利用上面处理大数的方法。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long a[1100][110],b[1100][110],inf;
int main(){
    int n,k,i,j;
    for(inf=1,i=0;i<18;i++) inf*=10;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
	scanf("%d%d",&n,&k);
	for(i=0;i<=k;i++) a[0][i]=1;
    for(i=1;i<=k;i++){
        for(j=1;j<=n;j++){
            if(j-i<0){
				b[j][i]=b[j][i-1];
				a[j][i]=a[j][i-1];
				continue;
			}
            b[j][i]=b[j][i-1]+b[j-i][i]+(a[j][i-1]+a[j-i][i])/inf;
            a[j][i]=(a[j][i-1]+a[j-i][i])%inf;
        }
    }
    if(b[n][k]) printf("%I64d",b[n][k]);
    printf("%I64d\n",a[n][k]);
    return 0;
}

其实我们还可以在空间上进行优化,看这个式子a[i][j]=a[i][j-1]+a[i-j][j]我们发现,如果外层循环式j实际上是上一次j在i的值,加上这次j在i-j的值,那么可以只开一维数组,代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long a[1100],b[1100],inf;
int main(){
    int n,k,i,j;
    for(inf=1,i=0;i<18;i++) inf*=10;
    scanf("%d%d",&n,&k);
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    a[0]=1;
    for(i=1;i<=k;i++){
        for(j=1;j<=n;j++){
            if(j-i<0) continue;
            b[j]=b[j]+b[j-i]+(a[j]+a[j-i])/inf;
            a[j]=(a[j]+a[j-i])%inf;
        }
    }
    if(b[n]) printf("%I64d",b[n]);
    printf("%I64d\n",a[n]);
    return 0;
}

这实际上是完全背包问题,只是状态转移方程形式有所不同,不过状态转移的方向是完全相同的。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就不用考虑这么多了,但是会相对慢些。

本文地址:http://www.nowamagic.net/librarys/veda/detail/441,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/441

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《程序员修炼之道:从小工到专家》 亨特(Andrew Hunt) (作者), 托马斯(David Thomas) (作者), 马维达 (译者)

《程序员修炼之道:从小工到专家》内容简介:《程序员修炼之道》由一系列独立的部分组成,涵盖的主题从个人责任、职业发展,知道用于使代码保持灵活、并且易于改编和复用的各种架构技术,利用许多富有娱乐性的奇闻轶事、有思想性的例子及有趣的类比,全面阐释了软件开发的许多不同方面的最佳实践和重大陷阱。无论你是初学者,是有经验的程序员,还是软件项目经理,《程序员修炼之道:从小工到专家》都适合你阅读。

更多计算机宝库...