UVA 10590（完全背包，整数拆分+大数加法）

大数加法一位位存效率很低会TLE，我是10亿10亿存的。

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
#include<queue>
#include<string>
using namespace std;

class bign
{
public:
	int a[10];
	int leng;
	void print();
	bign () {leng=0;memset(a,sizeof(a));}
	bign operator +(bign &b) const;
};

void bign::print()						
{
    int f=1;
	if(leng==0) printf("0");
	else
	for(int i=leng-1;i>=0;i--)
		{
		    if(f) printf("%d",a[i]);
		    else printf("%.9d",a[i]);
		    f=0;
		}
}

bign bign::operator +(bign &b) const
{
	int top=leng>b.leng?leng:b.leng;
	bign c;
	for(int i=0,g=0;i<top+1;i++)
	{
		long long s=a[i]+b.a[i]+g;
		g=0;
		if(s<1000000000) c.a[i]=s;
		else {c.a[i]=s%1000000000;g=s/1000000000;}
	}
	int j;
	for(j=top+2;;j--)
		if(c.a[j]!=0) break;
	c.leng=j+1;
	return c;
}

bign dp[5010];
int main()
{
    int n;
    dp[0].a[0]=1;
    dp[0].leng=1;
    for(int i=1;i<=5000;i++)
    {
        for(int j=i;j<=5000;j++)
        {
            dp[j]=dp[j]+dp[j-i];
        }
    }

    while(scanf("%d",&n)!=EOF)
    {
        dp[n].print();
        putchar(10);
    }

    return 0;
}