首页 > 代码库 > 【BZOJ 1021】 [SHOI2008]Debt 循环的债务

【BZOJ 1021】 [SHOI2008]Debt 循环的债务

2024-11-28 05:59:01   205人阅读

1021: [SHOI2008]Debt 循环的债务

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 605  Solved: 302
[Submit][Status]

Description

Alice、Bob和Cynthia总是为他们之间混乱的债务而烦恼，终于有一天，他们决定坐下来一起解决这个问题。不过，鉴别钞票的真伪是一件很麻烦的事情，于是他们决定要在清还债务的时候尽可能少的交换现金。比如说，Alice欠Bob 10元，而Cynthia和他俩互不相欠。现在假设Alice只有一张50元，Bob有3张10元和10张1元，Cynthia有3张20元。一种比较直接的做法是：Alice将50元交给Bob，而Bob将他身上的钱找给Alice，这样一共就会有14张钞票被交换。但这不是最好的做法，最好的做法是：Alice把50块给Cynthia，Cynthia再把两张20给Alice，另一张20给Bob，而Bob把一张10块给C，此时只有5张钞票被交换过。没过多久他们就发现这是一个很棘手的问题，于是他们找到了精通数学的你为他们解决这个难题。

Input

输入的第一行包括三个整数：x1、x2、x3（-1,000≤x1，x2，x3≤1,000），其中 x1代表Alice欠Bob的钱（如果x1是负数，说明Bob欠了Alice的钱） x2代表Bob欠Cynthia的钱（如果x2是负数，说明Cynthia欠了Bob的钱） x3代表Cynthia欠Alice的钱（如果x3是负数，说明Alice欠了Cynthia的钱）接下来有三行，每行包括6个自然数： a100，a50，a20，a10，a5，a1 b100，b50，b20，b10，b5，b1 c100，c50，c20，c10，c5，c1 a100表示Alice拥有的100元钞票张数，b50表示Bob拥有的50元钞票张数，以此类推。另外，我们保证有a10+a5+a1≤30，b10+b5+b1≤30，c10+c5+c1≤30，而且三人总共拥有的钞票面值总额不会超过1,000。

Output

如果债务可以还清，则输出需要交换钞票的最少张数；如果不能还清，则输出“impossible”（注意单词全部小写，输出到文件时不要加引号）。

Sample Input

输入一
10 0 0
0 1 0 0 0 0
0 0 0 3 0 10
0 0 3 0 0 0
输入二
-10 -10 -10
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Sample Output

输出一
5
输出二
0

HINT

对于100%的数据，x1、x2、x3 ≤ |1,000|。



dp。


首先要明确一点，这道题只可能有六种转移：

A-->BC 

B-->AC

C-->AB

BC-->A

AC-->B

AB-->C


为什么是这样呢？


比如A欠B10元，B欠C20元，那么直接A-->C10元，B-->C10元即可，也就是AB-->C；没必要A-->B10元，B-->C20元。


也就是说一张钱要直接给需要的人，不要有中转。


接下来就可以分这六种情况来dp了。


f[i][va][vb]表示用前i种钞票，使得A从初始到va,B从初始到vb的最小交换次数。


有一个优化是：


我们的目的是到达目标状态ea,eb,ec，而当前只能使用第i种到第6种钞票，求出他们的gcd=g，那么每次最少增加g，如

果无法通过va,vb每次增加g转移到ea,eb那么就不需要处理了。


#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#define inf 0x3f3f3f3f
#include <algorithm>
using namespace std;
int f[2][1005][1005],a[10],b[10],c[10],ea,eb,ec,sa,sb,sc,now,n,sum,m[10];
void read(int &tmp)
{
	tmp=0;
	int fu=1;
	char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar())
		if (ch=='-') fu=-1;
	for (;ch>='0'&&ch<='9';ch=getchar())
		tmp=tmp*10+ch-'0';
	tmp*=fu;
}
int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
void C(int &a,int b)
{
	if (a>b) a=b;
}
void Calc(int va,int vb,int k)
{
	int vc=sum-va-vb;
	//a-->bc
	for (int i=1;i<=a[k];i++)
	{
		if (va<i*m[k]) break;
		for (int j=0;j<=i;j++)
			if (vb+j*m[k]<=1000&&vc+(i-j)*m[k]<=1000)
				C(f[now^1][va-i*m[k]][vb+j*m[k]],f[now][va][vb]+i);
	}
	//b-->ac
	for (int i=1;i<=b[k];i++)
	{
		if (vb<i*m[k]) break;
		for (int j=0;j<=i;j++)
			if (va+j*m[k]<=1000&&vc+(i-j)*m[k]<=1000)
				C(f[now^1][va+j*m[k]][vb-i*m[k]],f[now][va][vb]+i);
	}
	//c-->ab
	for (int i=1;i<=c[k];i++)
	{
		if (vc<i*m[k]) break;
		for (int j=0;j<=i;j++)
			if (va+j*m[k]<=1000&&vb+(i-j)*m[k]<=1000)
				C(f[now^1][va+j*m[k]][vb+(i-j)*m[k]],f[now][va][vb]+i);
	}
	//bc-->a
	for (int i=0;i<=b[k];i++)
	{
		if (va+i*m[k]>1000||vb-i*m[k]<0) break;
		for (int j=0;j<=c[k];j++)
			if (va+(i+j)*m[k]<=1000&&vc-j*m[k]>=0)
				C(f[now^1][va+(i+j)*m[k]][vb-i*m[k]],f[now][va][vb]+i+j);
	}
	//ac-->b
	for (int i=0;i<=a[k];i++)
	{
		if (vb+i*m[k]>1000||va-i*m[k]<0) break;
		for (int j=0;j<=c[k];j++)
			if (vb+(i+j)*m[k]<=1000&&vc-j*m[k]>=0)
				C(f[now^1][va-i*m[k]][vb+(i+j)*m[k]],f[now][va][vb]+i+j);
	}
        //ab-->c
	for (int i=0;i<=b[k];i++)
	{
		if (vc+i*m[k]>1000||vb-i*m[k]<0) break;
		for (int j=0;j<=a[k];j++)
			if (vc+(i+j)*m[k]<=1000&&va-j*m[k]>=0)
				C(f[now^1][va-j*m[k]][vb-i*m[k]],f[now][va][vb]+i+j);
	}
}
void dp()
{
	now=0;
	for (int i=0;i<=1000;i++)
		for (int j=0;j<=1000;j++)
			f[now][i][j]=inf;
	f[now][sa][sb]=0;
	if (ea<0||eb<0||ec<0)
	{
		printf("impossible\n");
		return;
	}
	for (int i=1;i<=6;i++)
	{
		for (int j=0;j<=1000;j++)
			for (int k=0;k<=1000;k++)
				f[now^1][j][k]=f[now][j][k];
		int g=m[i],x,y;
		for (int j=i+1;j<=6;j++)
			g=gcd(g,m[j]);
		for (x=0;(ea-x)%g;x++);
		for (y=0;(eb-y)%g;y++);
		if ((ec-(sum-x-y))%g) continue;
		for (int j=x;j<=1000;j+=g)
		{
			if (sum-j-y<0) break;
			for (int k=y;k<=1000;k+=g)
			{
				int vc=sum-j-k;
				if (vc<0) break;
				if (f[now][j][k]==inf) continue;
				Calc(j,k,i);
			}
		}
		now^=1;
	}
	if (f[now][ea][eb]==inf) printf("impossible\n");
	else printf("%d\n",f[now][ea][eb]);
}
int main()
{
	m[6]=100,m[5]=50,m[4]=20,m[3]=10,m[2]=5,m[1]=1;
	int x1,x2,x3;
        read(x1),read(x2),read(x3);
	for (int i=6;i;i--)
		read(a[i]),sa+=a[i]*m[i];
	for (int i=6;i;i--)
		read(b[i]),sb+=b[i]*m[i];
	for (int i=6;i;i--)
		read(c[i]),sc+=c[i]*m[i];
	ea=sa-x1+x3,eb=sb+x1-x2,ec=sc-x3+x2;
	sum=sa+sb+sc;
	dp();
	return 0;
}

技术分享


感悟:

1.WA是因为sa,sb,sc求错。。


2.gcd的优化值得借鉴：无论如何都到不了目标状态的情况不必转移

【BZOJ 1021】 [SHOI2008]Debt 循环的债务


联系
我们