题意：

给你 nnn 条直线
保证：没有三条线共享一个共同点，并且没有线是重合的。
问你：所有可能交叉点的数量

解决这个问题的前提需能解决
HDU1466

两个问题直接的最关键的差别是 nnn 的大小

我们先去分析 HUD1466
n≤20n \le 20n≤20

我们可以得到一个数学式子：

如果x条线相互平行，另外y条线任意（但不与这x条线平行）的话，

总的交点数就是y条线自己产生的交点数 + x * y，

原因就是y条线中的每条线都与x条平行线产生x个交点。

我们可以使用动态规划来解决这一道题：

设 dp[i,j]dp[i,j]dp[i,j] 为用 iii 条直线产生 jjj 个交点是否可行，kkk 为 iii 条线中相互平行的线的数量，则转移方程为: dp[i,j]∣=dp[i−k,j−(i−k)×k]dp[i,j] |= dp[i−k,j−(i−k)×k]dp[i,j]∣=dp[i−k,j−(i−k)×k]。其中 i−ki - ki−k 就是任意的线的数量，(i−k)∗k(i - k) * k(i−k)∗k就是任意的线与平行线产生的交点数。

AC 代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define buff                     \ios::sync_with_stdio(false); \cin.tie(0);
//#define int long long
//#define ll long long
#define PII pair
#define px first
#define py second
typedef std::mt19937 Random_mt19937;
Random_mt19937 rnd(time(0));
using namespace std;
const int mod = 1e9 + 7;
const int N = 100009;
int dp[25][25 * 25];
void solve()
{// for (int i = 1; i <= 20; i++)//     dp[i][0] = 1;for (int i = 1; i <= 20; i++){dp[i][0] = 1;for (int j = 1; j < i; j++){int m = i - j; // 自由线段for (int k = 0; k <= m * (m - 1) / 2; k++){if (dp[m][k])dp[i][m * j + k] = 1;// dp[i][m * j + k] |= dp[m][k];  或这样写}}}
}
int main()
{buff;solve();int n;while (cin >> n){for (int i = 0; i <= n * (n - 1) / 2; i++){if (dp[n][i])cout << i << " \n"[i == n * (n - 1) / 2];}}
}

nnn 大的时候如何优化：

上面 dp 的时间复杂度为: O(n4)O(n^4)O(n4)
我们可以使用bitset进行优化：
那么借助 bitset，我们可以把它优化成 O(n2/w）O(n^2/w）O(n2/w）
对于每一个 iii 维护一个bitset, bitset的大小为 n×(n−1)2n×(n−1)2n×(n−1)2，在循环里直接省略掉原先的第二重循环，同时把转移方程的写法改为dp[i]=dp[i]∣dp[i−k]<<((i−k)∗k)dp[i] = dp[i] | dp[i - k] << ((i - k) * k)dp[i]=dp[i]∣dp[i−k]<<((i−k)∗k);

这样改完运行还是慢，跑完大概需要几秒时间吧
为什么？
因为我们bitset开很大！！！

当n∗n/2≥31500n * n / 2 \ge 31500n∗n/2≥31500 的时候

n 大于等于一定值时

后面的数都是连续的
这个可以打表看出来！

题解给的界限是31500，这样的话bitset实际上只需要开到这个上界就足矣，i大于上界的话直接输出即可，这样就能通过本题了。

AC代码：

#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define buff                     \ios::sync_with_stdio(false); \cin.tie(0);
//#define int long long
//#define ll long long
#define PII pair
#define px first
#define py second
typedef std::mt19937 Random_mt19937;
Random_mt19937 rnd(time(0));
using namespace std;
const int mod = 1e9 + 7;
const int N = 31500 + 9; // 题解给的界限是31500
bitset dp[709];
void solve()
{for (int i = 0; i <= 700; i++)dp[i][0] = 1;for (int i = 1; i <= 700; i++){for (int j = 0; j < i; j++){dp[i] = dp[i] | (dp[i - j] << ((i - j) * j));}}
}
int main()
{buff;solve();int _;cin >> _;while (_--){int n;  cin >> n;for (int i = 0; i <= n * (n - 1) / 2; i++)if (i >= 31500 || dp[n][i])cout << i << " \n"[i == n * (n - 1) / 2];}
}

感谢：
脂环
参考文章

上一篇：Android Jetpack Compose——一个简单的聊天界面

下一篇：时间序列建模三部曲

2021“MINIEYE杯”中国大学生算法设计超级联赛（10）Pty loves lines（动态规划 | DP）

题意：

AC 代码：

nnn 大的时候如何优化：

AC代码：

相关内容

热门资讯