【动态规划】串联电阻

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列开始输出。

【输入输出样例】

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

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

#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;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!