Description
1 @ US$3 + 1 @ US$2Write a program than will compute the number of ways FJ can spend N dollars (1 <= N <= 1000) at The Cow Store for tools on sale with a cost of $1..$K (1 <= K <= 100).
1 @ US$3 + 2 @ US$1
1 @ US$2 + 3 @ US$1
2 @ US$2 + 1 @ US$1
5 @ US$1
Input
Output
题解：
dp+高精加
显然完全背包dp，dp[j]+=dp[j-i]
需要高精加法
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const int N = 1010;
int dp[N][110];
int gi() {
int x=0,o=1; char ch=getchar();
while(ch!=‘-‘ && (ch<‘0‘ || ch>‘9‘)) ch=getchar();
if(ch==‘-‘) o=-1,ch=getchar();
while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();
return o*x;
}
void plu(int x, int y) {
int c=0,k=max(dp[x][0],dp[y][0]);
for(int i=1; i<=k; i++) {
dp[x][i]=dp[x][i]+dp[y][i]+c;
c=dp[x][i]/10;
dp[x][i]%=10;
}
dp[x][0]=k;
while(c) {
dp[x][++dp[x][0]]=c%10;
c/=10;
}
}
int main() {
int m=gi(),n=gi();
dp[0][0]=1,dp[0][1]=1;
for(int i=1; i<=n; i++)
for(int j=i; j<=m; j++)
plu(j,j-i);
for(int i=dp[m][0]; i>=1; i--)
printf("%d", dp[m][i]);
return 0;
}
原文：http://www.cnblogs.com/HLXZZ/p/7509472.html