4、串联电阻（resist.pas/cpp）

【题目描述】

一家电子商店计划购入若干盒电阻器，每盒至少有2500个阻值相同的电阻，不同盒子中的电阻阻值不同。他们计划购入4至20盒，其中一盒装着阻值为1 kΩ的电阻，但他们尚未确定其他盒子中电阻的阻值。

如果你把电阻串联起来，所得新电阻的阻值等于原来各电阻值之和。例如，你串联（以任何顺序）3个500 kΩ，2个200 kΩ，1个50 kΩ，2个20 kΩ，1个5 kΩ和2个2 kΩ的电阻，就会得到阻值为199 9kΩ的等效电阻。类似地，你可以用2个2 kΩ和1个1 kΩ的电阻或者5个1 kΩ的电阻来代替原来那个1个5 kΩ的电阻而不改变总电阻的阻值。为了决定需要购买多少盒及每盒中电阻的阻值，商店想在已给出的一种购买方案的情况下，计算出用串联的方法获得各种阻值电阻的容易程度。也就是说，给出盒子的数量b和各盒中电阻的阻值1=v₁<v₂<…<v_b，他们想知道对于若干个阻值n，分别有多少种串联方法可以获得阻值为n的电阻，单位为kΩ。

【输入格式：】

输入文件包含若干方案。每个方案以一个整数b(1≤b ≤20)开始。b等于0表示文件结束。方案的第2行是b个按递增顺序排列的整数，以1开始，按顺序分别代表v₁到v_b。接下来的若干行每行都有一个整数n，代表需要串联获得的电阻值，范围从1到1999，以0结束，这里的0不被处理。

【输出格式】

对输入文件中的每个阻值n，输出串联获得n kΩ电阻的方法总数，每个数一行，且均从每一行的第1列开始输出。

【输入输出样例】

其实这是一个完全背包。。一开始没看出来。。。

只是由求最大值变成了求和。要用高精度。

@H_403_124@#include <cstdio> #include <cstring> #include <string> #define MAX(a,b) ((a)>(b)?(a):(b)) long w[30]; long r[10000000]; long getint() { long rs=0;bool sgn=1;char tmp; do tmp = getchar(); while (!isdigit(tmp)&&tmp-'-'); if (tmp=='-'){tmp=getchar();sgn=0;} do rs=(rs<<3)+(rs<<1)+tmp-'0'; while (isdigit(tmp=getchar())); return sgn?rs:-rs; } struct Big { long num[50]; void operator+=(Big& b) { num[0] = num[0]>b.num[0]?num[0]+1:b.num[0]+1; for (long i=1;i<num[0]+1;i++) { num[i] += b.num[i]; if (num[i]>9) { num[i]-=10; num[i+1]++; } } if (num[num[0]] == 0) num[0]--; } void operator=( long b) { memset(num,sizeof num); while (b) { num[++num[0]] = b%10; b /= 10; } } void print() { for (long i=num[0];i>0;i--) printf("%ld",num[i]); printf("\n"); } }; Big f[2012]; int main() { freopen("resist.in","r",stdin); freopen("resist.out","w",stdout); long maxr = 0; while (1) { long n = getint(); if (n == 0) break; for (long i=1;i<n+1;i++) w[i] = getint(); for (long i=1;i<maxr+1;i++) f[i] = 0; f[0] = 1; long rcnt = 0; while (1) { r[++rcnt] = getint(); maxr = MAX(maxr,r[rcnt]); if (r[rcnt] == 0) { rcnt--; break; } } for (long i=1;i<n+1;i++) { for (long j=1;j<maxr+1;j++) { if (j-w[i]>=0) { f[j] += f[j-w[i]]; } } } for (long i=1;i<rcnt+1;i++) f[r[i]].print(); } return 0; }