记录编号	22321	评测结果	AAAWEEEEWE
题目名称	情敌	最终得分	30
用户昵称	了反取字名我擦	是否通过	未通过
代码语言	C++	运行时间	0.016 s
提交时间	2010-11-18 16:08:41	内存使用	0.27 MiB

#include<fstream>
using namespace std;
ifstream fi("rival.in");
ofstream fo("rival.out");
int a,b,n,m,x[53]={0},t[53]={0},t1,t2,t3[53]={0},data[53][53]={0},f1[5][101]={0},p=0;
int f2[5][101]={0},f3[5]={0},ans=0;
bool prot[53]={0};
int M(int a,int b)
{
	if(a>b)
		return a;
	else
		return b;
}
int M(int a,int b,int c)
{
	if(a>=b&&a>=c)
		return a;
	if(b>=a&&b>=c)
		return b;
	if(c>=a&&c>=b)
		return c;
}
void fz()
{
	int temp[100][100]={0};
	for(int i=0;i<m;i++)
	{
		fi>>t1>>t2;
		for(int j=0;j<t2;j++)
		{
			fi>>t3[j];
			prot[t3[j]]=1;
		}
		for(int pri=0;pri<=M(a,b)-x[t1];pri++)
		{
			for(int j=0;j<t2;j++)
				for(int k=pri;k>=0;k--)
					if(k-t[t3[j]]>=0)
						temp[pri][k]=M(temp[pri][k],temp[pri][k-t[t3[j]]]+x[t3[j]]);
			f1[i][pri]=x[t1]+temp[pri][pri];
			f2[i][pri]=t[t1]+pri;
			f3[i]=x[t1];
		}
	}
}
int main()
{
	fi>>a>>b>>n>>m;
	for(int i=1;i<=n;i++)
		fi>>x[i]>>t[i];
	fz();
	for(int i=1;i<=n;i++)
		if(!prot[i])
			for(int j=a;j>=0;j--)
				for(int k=b;k>=0;k--)
					if(j-t[i]>=0&&k-2*t[i]>=0)
						data[j][k]=M(data[j][k],data[j-t[i]][k]+x[i],data[j][k-2*t[i]]+x[i]);
					else
						if(j-t[i]>=0)data[j][k]=M(data[j][k],data[j-t[i]][k]+x[i]);
						else if(k-2*t[i]>=0)data[j][k]=M(data[j][k],data[j][k-2*t[i]]+x[i]);
	for(int i=0;i<m;i++)
		for(int j=0;f1[i][j]!=0;j++)
			for(int k=a;k>=0;k--)
				for(int l=b;l>=0;l--)
					if(k-f2[i][j]>=0&&l-2*f2[i][j]>=0)
						data[k][l]=M(M(data[k][l],data[k-f2[i][j]][l]+f1[i][j],data[k][l-2*f2[i][j]]+f1[i][j]),data[k-f3[i]][l+2*f3[i]-2*f2[i][j]]+f1[i][j]);
					else
					{
						if(k-f2[i][j]>=0&&l+2*f3[i]-2*f2[i][j]>=0)
							data[k][l]=M(data[k][l],data[k-f2[i][j]][l]+f1[i][j],data[k-f3[i]][l+2*f3[i]-2*f2[i][j]]+f1[i][j]);
						else
							if(k-f3[i]>=0&&l+2*f3[i]-2*f2[i][j]>=0)
								data[k][l]=M(data[k][l],data[k-f3[i]][l+2*f3[i]-2*f2[i][j]]+f1[i][j]);
							else
								if(k-f3[i]<0&&l-2*f2[i][j]>=0)
									data[k][l]=M(data[k][l],data[k][l-2*f2[i][j]]+f1[i][j],data[k-f3[i]][l+2*f3[i]-2*f2[i][j]]+f1[i][j]);
								else
									if(k-f3[i]<0&&l-2*f2[i][j]+2*f3[i]>=0)
										data[k][l]=M(data[k][l],data[k-f3[i]][l+2*f3[i]-2*f2[i][j]]+f1[i][j]);
					}
	for(int i=1;i<=n;i++)
		ans+=x[i];
	ans-=data[a][b];
	fo<<ans;
	fi.close();
	fo.close();
	return 0;
}