pku1275.cpp

内有pku1201

////POJ1275 Cashier Employment 
//查分约束

#include <stdio.h>
#include <string.h>

const int M=25,Me=200,NO=123456789;

int sum[M];
int a[M],b[M];
int map[M][M];

int Can(int s)
{
	memset(sum, 0, sizeof(sum));
	int i,j,k;
         map[0][24]=s;
	for (i=1;i<=8;++i)
		map[i+16][i]=a[i]-s;
	k=0;
	while (k++<M)
	{
		bool f=true;
		for (i=0;i<M;++i)
			for (j=M-1;j>=0;j--)
				if (map[i][j]!=NO && sum[j] < sum[i] + map[i][j])
				{
					f=false;
					sum[j] = sum[i] + map[i][j];
				}
              if(f) return true;
	}
	return false;

}
int main()
{
	int Case,i,j,k;
	scanf("%d",&Case);
	while (Case--)
	{
		for (i=0;i<M;++i)
			for (j=0;j<M;++j)
				map[i][j]=NO;
		for (i=1;i<M;++i)
			scanf("%d",a+i);
		memset(b, 0, sizeof(b));
		scanf("%d",&k);
		for (i=1;i<=k;++i)
		{
			scanf("%d",&j);
			++b[j+1];
		}
		for (i=1;i<M;++i)
			map[i-1][i]=0;
		for (i=1;i<M;++i)
			map[i][i-1]=-b[i];
		for (i=9;i<M;++i)
			map[i-8][i]=a[i];

		int left=0,right=k,mid;
		while (right != left)
		{
			mid = (left+right)>>1;
			if (Can(mid))	right=mid;
			else			left=mid+1;
		}
		if (Can(right))	printf("%d\n",right);
		else	printf("No Solution\n");
	}
	return 0;
}