poj 3181 Dollar Dayz (完全背包+高精度）

题意：求将n分解为大于等于1小于等于k的数，有多少种分法。（划分数问题）

分析：

1、可以用完全背包解。

for(i=1...k)

      for(j=i...n)

            dp[j]+=dp[j-i]；

由于1<=n<=1000，1<=k<=100，所以数据巨大，__int64 也表示不了。

故用两个long long 来表示。

2、可以用划分数的思想。

dp[n][m]表示把n分为若干份，且最大的那份<=m的方案数。

1、当m=1，n=1时，dp[n][m]=1

2、当m=n时，dp[n][m]=dp[n][n]，dp[n][n]=dp[n][n-1]+1

3、当m>n时，dp[n][m]=dp[n][n]

4、m<n时，dp[n][m]=dp[n-m][m]+dp[n][m-1]

前者表示划分中有一个数为m，后者表示划分中所有的数都小于m，即所有的数都<=m-1。

dp[0][0...k]=1；0只有1种分法。

3、高精度的处理也可以用java。

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const long long INF=1000000000000000000LL;
long long a[1010],b[1010];

int main()
{
    int n,k;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        b[0]=1;
        for(int i=1;i<=k;i++)
        {
            for(int j=i;j<=n;j++)
            {
                a[j]=a[j]+a[j-i]+(b[j]+b[j-i])/INF;
                b[j]=(b[j]+b[j-i])%INF;
            }
        }
        if(a[n]) printf("%I64d",a[n]);
        printf("%I64d\n",b[n]);
    }
    return 0;
}

java并不精通，还在学习中。。。

看了别人用java AC的代码。

收获：1、java中memset（）用 Arrays.fill（）来代替。

2、大数的表示BigInteger.ZERO、 BigInteger.ONE （后面的要大写）

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	final static int maxn = 1005;
	
	public static void main(String[] args) {
		
		Scanner cin = new Scanner(System.in);
		while (cin.hasNext()){
			int n, k;
			n = cin.nextInt();
			k = cin.nextInt();
			
			BigInteger[] dp = new BigInteger[maxn];
			Arrays.fill(dp, BigInteger.ZERO);
			dp[0] = BigInteger.ONE;
			for (int i=1; i<=k; i++)
				for (int j=0; i+j<=n; j++)
					dp[i+j] = dp[i+j].add(dp[j]);
			System.out.println(dp[n]);
		}
		
	}

}

还学习到   模拟高精度加法    ac这题的做法：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;

int dp[1010][100];

void ADD(int n,int m)
{
    for(int i=0;i<60;i++)
    {
        dp[n][i]+=dp[m][i];
        if(dp[n][i]>=10)
        {
            dp[n][i]%=10;
            dp[n][i+1]++;
        }
    }
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=1;i<=m;i++)
          for(int j=i;j<=n;j++)
            ADD(j,j-i);
        int t=60;
        while(t>0&&dp[n][t]==0)t--;
        for(int i=t;i>=0;i--)printf("%d",dp[n][i]);
        printf("\n");
    }
    return 0;
}

参考blog:

http://www.cnblogs.com/kuangbin/archive/2012/09/20/2695165.html

http://blog.csdn.net/liuqiyao_01/article/details/8928550

poj 3181 Dollar Dayz (完全背包+高精度）

原文：http://blog.csdn.net/u012841845/article/details/19005087