鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 手机系统开发 > J2ME > >

Hdu 1398 Square Coins//整数划分(二)

来源:互联网 作者:佚名 时间:2015-09-25 05:46
这道题对 整数 能够拆分的数有个限制,必须是完全平方数,但是只需要稍微改动一点就可以做了。PS:其实我想用母函数做的,但是代码有点多,o(╯□╰)o! 下面是代码: /*Hdu 1398 Square Coins 整数 划分 PS:赶脚自己的代码写的有点繁琐,o(╯□╰)o!*/#in

这道题对整数能够拆分的数有个限制,必须是完全平方数,但是只需要稍微改动一点就可以做了。PS:其实我想用母函数做的,但是代码有点多,o(╯□╰)o!

下面是代码:

/*Hdu 1398 Square Coins
    整数划分
    PS:赶脚自己的代码写的有点繁琐,o(╯□╰)o!
*/
#include<iostream>
using namespace std;
const int maxn = 310;
int n;
int f[maxn][maxn];
int main()
{
    while(cin>>n)
    {
        if(!n) break;
        for(int i = 0; i <= n; i++)
        {
            for(int j = 0; j <= n; j++)
            {
                 f[i][j] = 0;
            }
        }
        f[1][1] = 1;
        for(int i = 2; i <= n; i++)
        {
            for(int j = 1; j*j <= i; j++)
            {
                int p = j*j;
                int q = (j-1)*(j-1);
                if(i == p) f[i][p] = f[i][q] + 1;
                else
                {
                    if(i - p <= p) f[i-p][p] = f[i-p][i-p];
                    f[i][p] = f[i][q] + f[i-p][p];
                }
                f[i][i] = f[i][p];
            }
        }
        for(int i = n; i >= 1; i--)
        {
            if(f[n][i] != 0)
            {
                cout<<f[n][i]<<endl;
                break;
            }
        }
    }
    return 0;
}



网友评论
<