题意：求将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
前者表示划分中有一个数为m，后者表示划分中所有的数都小于m，即所有的数都<=m-1。
dp[0][0...k]=1；0只有1种分法。
3、高精度的处理也可以用java。
#include#include #include 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#include #include #include 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