1717.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1717 on 2006-06-05 at 12:11:59 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int LN = 128, CN = 5120;
const int NINF = - 1<<29;

int p[LN][CN];

int cross(int, int);

int main()
{
	int n, m, t;

	memset(p, 0, sizeof(p));
	for(t = 1; scanf("%d %d", &n, &m) != EOF && n != 0; t++) {
		int r = cross(n, m);
		printf("Case %d: %d lines ", t, n);
		if(r < 0) printf("cannot make exactly %d crossings.\n", m);
		else printf("with exactly %d crossings can cut the plane into %d pieces at most.\n", m, r);
	}
	
	return 0;
}

int cross(int n, int k)
{
	int i;
	if(2*k > n*(n-1)) return NINF;
	else if(k == 0) p[n][k] = n+1;
	else if(p[n][k] == 0)
		for(i = n-1; i > 0; i--)
			if(k >= i*(n-i)) p[n][k] = max(p[n][k], cross(n-i, k-i*(n-i))+i*(n-i+1));
	if(p[n][k] == 0) p[n][k] = NINF;
	return p[n][k];
}