[SHOI2008]循环的债务

题目

思路

注意到这道题中A,B,C拥有的钱的最终状态是可以确定的

将不同种类的钱分开讨论，设(f[k][i][j])表示考虑了前k种钱，A有i元，B有j元的最小交换次数，初值(f[0][0][0]=0)，目标是(f[6][lasta][lastb])，(last)表示最终的钱数，模拟一下很容易转移，，，然而BZOJ上面好像会TLE不知道为什么，洛谷上可以过

#include<bits/stdc++.h>
#define re register
#define Min(x,y) ((x)<(y) ? (x):(y))
#define Abs(x) ((x)>0 ? (x):(-(x)))
using namespace std;
int x[4],sump[4],summ[7];
int a[4][7],val[7]={0,100,50,20,10,5,1};
int f[7][1002][1002];//前k种钱，A有i元，B有j元的次数 


template <class T>
void read(T &x)
{
	char c;int sign=1;
	while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
	while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}


int main()
{
	for(int i=1;i<=3;++i) read(x[i]);
	for(int i=1;i<=3;++i)
	{
		for(int j=1;j<=6;++j)
		{
			read(a[i][j]);
			sump[i]+=a[i][j]*val[j];
			summ[j]+=a[i][j];
		}
	}
	//算出最后A,B,C的钱 
	sump[1]=sump[1]-x[1]+x[3];
	sump[2]=sump[2]-x[2]+x[1];
	sump[3]=sump[3]-x[3]+x[2];
	int S=0;
	memset(f,100,sizeof(f));
	f[0][0][0]=0;
	for(re int k=0;k<6;++k)
	{
		for(re int i=0;i<=S;++i)
		{
			for(re int j=0;i+j<=S;++j)
			{
				if(f[k][i][j]<100000000)
				for(re int o=0;o<=summ[k+1];++o)
				{
					for(re int p=0;p+o<=summ[k+1];++p)
					{
						re int cc=Abs(o-a[1][k+1])+Abs(p-a[2][k+1])+Abs(summ[k+1]-o-p-a[3][k+1]);
						f[k+1][i+o*val[k+1]][j+p*val[k+1]]=Min(f[k+1][i+o*val[k+1]][j+p*val[k+1]],f[k][i][j]+(cc>>1));
					}
				}
			}
		}
		S+=summ[k+1]*val[k+1];
	}
	if(sump[1]<0||sump[2]<0||sump[3]<0||f[6][sump[1]][sump[2]]>100000000) cout<<"impossible"<<endl;
	else cout<<f[6][sump[1]][sump[2]]<<endl;
	return 0;
}