[hdu] P7079 Pty loves lines

题目链接

经典的求直接交点数的问题
之前做过简化版 ，并且安利一下自己的题解

如果依旧像之前一样用二维dp[i][j]表示能否达到i条直线，j个交点的情况，将面临运行超时，dp数组存不下的尴尬局面。那么考虑新的做法。

考虑讲n条直线划分为若干组，每一组内的直线两两平行且这个组是极大的。设总共分成了 $p$ 组，每一组的直线数为 $a_i$，那么交点数就是$\frac{n(n-1)}{2}-{\sum }_{i=1}^k\frac{a_i(a_i-1)}{2}$，且${\sum }_{i=1}^p{a}_i=n$。因为如果n条直线两两相交，共有 $\frac{n(n-1)}{2}$ 个交点，每一组里是没有交点的，减去即可。
观察$\frac{n(n-1)}{2}-{\sum }_{i=1}^k\frac{a_i(a_i-1)}{2}$，只要考虑${\sum }_{i=1}^k\frac{a_i(a_i-1)}{2}$的所有取值，即可得到所有可能的交点数。
设$f(n)$为 $\sum \frac{a_i(a_i-1)}{2}$ 取$n$时 $\sum a_i$ 的最小值，有递推关系：$f(n)=min\{f(n-\frac{k(k-1)}{2})+k\}$。预处理f[]，从$\frac{n(n-1)}{2}$倒序枚举j，判断j能否取到，能取到就输出$\frac{n(n-1)}{2}-j$。

完整代码：
（官方的标程个人感觉可读性不强）

#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF 0x3f3f3f3f
typedef long long ll;
const int maxn = 3e7+5;

using namespace std;

int kase,n;
const int m=700;
int f[maxn];

int main()
{
    
   	FAST; 
	memset(f,INF,sizeof(f));
	
	f[0]=0;
	for (int i=1; i<=m*(m-1)/2; i++)
	{
    
		for (int k=2; k*(k-1)<=2*i; k++)
			f[i]=min(f[i],f[i-k*(k-1)/2]+k);
	}
	
	cin>>kase;
	while(kase--)
	{
    
		cin>>n;
		for (int i=n*(n-1)/2; i>=1; i--)
			if (f[i]<=n) cout<<n*(n-1)/2-i<<' ';
		cout<<n*(n-1)/2<<endl;
	}
return 0;
}