1923.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include<stdio.h>
#include<string.h>
__int64 line[101][10001];
int com(int a)
{
	return a*(a-1)/2;
}
int main()
{
	//freopen("1923.txt","r",stdin);
	int i,j,k,p,q,cs=0;
    __int64 max,tmp;
	memset(line,0,sizeof(line));
	for(i=1;i<=100;i++)
		line[i][0]=i+1;
	for(i=2;i<=100;i++)
	   for(j=1;j<=com(i);j++)
	   {
		   max=0;
		   for(k=1;k<=i-1;k++)
		   {
			   p=i-k;q=j-k*p;
			   if(q>=0)
			   {
				   if(line[p][q]!=0)
				   {
				   tmp=line[p][q]+k*(p+1);
				   if(tmp>max)
					   max=tmp;
				   }
			   }
		   }
		   line[i][j]=max;
	   }
	while (scanf("%d%d",&i,&j)!=EOF)
	{
		if(i==0&&j==0)
			break;
		cs++;
		if(line[i][j]>0)
			printf("Case %d: %d lines with exactly %d crossings can cut the plane into %I64d pieces at most.\n",cs,i,j,line[i][j]);
		else printf("Case %d: %d lines cannot make exactly %d crossings.\n",cs,i,j);
	}
	return 0;
}