A. POJ 1923 Fourier‘s Lines
题意简述
试判断 n 条任意（不重合）直线是否可能形成 m 个交点，满足任意一个交点只有两条直线经过？如果是，并输出此种情况下，平面最多能被切成几份。
解题报告
直线之间产生交点当且仅当直线斜率不同
所以对于 \(n\) 条已经确定的直线，先把其中一类斜率全相同的直线拿出来，记有 \(i\) 条，那么剩下 \((n - i)\) 条直线的斜率一定和那 \(i\) 条都不相同，每一条都能贡献 \(i\) 个交点（一个交点只有两条直线经过），它们产生的贡献就是 \(i(n - i)\)；而剩下的 \((n - i)\) 条直线内部又可以产生贡献，递归计算即可
实现是记忆化搜索
代码实现
int n, m;
char dp[100 + 10][10000 + 10]; // i 条线 j 个交点 是否存在方案
char dfs(int n, int m) {
// n 条直线里拿出一类斜率相同的直线共 i 条，剩下 (n - i) 条直线
// 交点个数为 i * (n - i) 加上 (n - i) 条直线内部形成的交点个数
if (m < 0 || m > ((n * (n - 1)) >> 1)) return 0;
if (!m) return 1;
if (dp[n][m] != -1) return dp[n][m];
for (int i = 1; i <= n - 1; ++i) {
if (dfs(n - i, m - i * (n - i)))
return dp[n][m] = 1;
} return dp[n][m] = 0;
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int cas = 0;
while (true) {
cin >> n >> m;
if (n == 0 && m == 0) break;
memset(dp, -1, sizeof dp);
cout << "Case " << ++cas << ": ";
if (dfs(n, m)) cout << n << " lines with exactly " << m << " crossings can cut the plane into " << n + m + 1 << " pieces at most." << endl;
else cout << n << " lines cannot make exactly " << m << " crossings." << endl;
}
return 0;
}