bzoj1655[Usaco2006 Jan] Dollar Dayz 奶牛商店
題意:
商場裡有K種工具,價格分别為1,2,…,K美元。約翰手裡有N美元,必須花完。求購買組合方案。n≤1000,k≤100。
題解:
完全背包,不過要高精度。
代碼:
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <queue>
5 #define inc(i,j,k) for(int i=j;i<=k;i++)
6 #define maxn 1010
7 #define ll long long
8 using namespace std;
9
10 inline int read(){
11 char ch=getchar(); int f=1,x=0;
12 while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
13 while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
14 return f*x;
15 }
16 struct bigint{
17 int len,num[100];
18 void operator = (int a){len=0; memset(num,0,sizeof(num)); while(a)num[++len]=a%10,a/=10;}
19 void operator = (bigint a){
20 memset(num,0,sizeof(num)); inc(i,1,a.len)num[i]=a.num[i]; len=a.len;
21 }
22 void operator += (bigint a){
23 len=max(len,a.len);
24 inc(i,1,len){num[i]+=a.num[i]; if(num[i]>=10)num[i+1]+=num[i]/10,num[i]%=10;}
25 if(num[len+1])len++;
26 }
27 void print(){for(int i=len;i>=1;i--)printf("%d",num[i]);}
28 };
29 int n,k,x,y; bigint f[2][maxn];
30 int main(){
31 n=read(); k=read(); x=0; y=1; f[x][0]=1;
32 inc(i,1,k){
33 inc(j,0,n)f[y][j]=f[x][j]; inc(j,i,n)f[y][j]+=f[y][j-i]; swap(x,y);
34 }
35 f[x][n].print(); return 0;
36 }
20160927
轉載于:https://www.cnblogs.com/YuanZiming/p/5966611.html