【动态规划】串联电阻

前端之家收集整理的这篇文章主要介绍了【动态规划】串联电阻前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

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=v1<v2<…<vb,他们想知道对于若干个阻值n,分别有多少种串联方法可以获得阻值为n的电阻,单位为kΩ。

【输入格式:】

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

输出格式】

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

【输入输出样例】

输入

输出

9

1 2 5 10 20 50 100 200 500

1

5

10

42

50

137

500

1999

0

4

1 2 3 4

1

10

3

2

0

0

1

4

11

271

451

15154

6295435

27888185754

1

23

3

2


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

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


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

猜你在找的VB相关文章