首页 > 代码库 > bzoj1655[Usaco2006 Jan] Dollar Dayz 奶牛商店*
bzoj1655[Usaco2006 Jan] Dollar Dayz 奶牛商店*
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
bzoj1655[Usaco2006 Jan] Dollar Dayz 奶牛商店*
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。