算法基础-dfs的经验

dfs的经验

我总感觉dfs和递归是一个东西
洛谷递归的好题

void dfs(int cur, int res)//假设当前枚举到第u层，即我们当前枚举的就是第u种平行线
{
    if (cur == 0) 
    {
        if (vis[res] == 0) ans ++;
        vis[res] = 1;  return;
    }
    else
    {
        for (int i = 0; i < cur; ++ i)//当前第u种平行线共有cur条线，我们取其中的i条线变成与第u中平行线不平行，
        {
        //无论i条线和第u种平行线剩下的u-i条线是否平行，它与前u-1种平行线都是相交的，本层新增的交点数是当前枚举的i条线和第u种平行线剩下的u-i条线相交获得的，即 i * (cur - i)
            dfs(i, i * (cur - i) + res);//其实就是回溯，可以把i * (cur - i)拆出来写，下面恢复现场就行了
        }
    }
}
void solve()
{
    cin >> n;
    dfs(n, 0);
    cout << ans ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22