eightgon题解,思维.

Eightgon题解:
题意:
要求在点的集合里面选择八个点建造,的每个点上都有一个特殊机器,使粒子速度向左偏转45°.问有几种建造**的方式.

思路:
题目就是要我们求可以构成相邻两条边夹角是135°的八边形的数量.
思路:
用dp[i][j][k]来表示从i点开始花费了k条边到达j点的路径数量,
有递推式

等式后面的∑b代表的是符合条件:以b为顶点,c在其合法的射线上.( 合法的射线指的是射线bc或平形于x轴,或垂直x轴,或于x轴夹角为45°+/-k90°(k>0) ).
dp[i][i][8]即为i点作为顶点之一可以构成八边形的数量,但这样不仅重复,还会超时,时间复杂度是O(n^3).
优化:将所有点按八个方向分别排序,依次遍历八个方向,用dp[i][j]记录在该方向上排j点之前的点花费i条线到达j点的方案数.
递推式

    dp[d+1][j]=dp[d][last] + dp[d+1][last];
    //递推式的第一项表示从last点到点j,粒子改变了方向的方案数;第二项表示从last到j点粒子没有改变方向的方案数.

每遍历完一个方向后就加上dp[8][start] (start为起点.)这样也不会有重复计算八边形的数量.
代码:

#include<algorithm>
#include<iostream>
#include<vector>

// 时间复杂度: O(n^2)
// 该题主要思维和学习处理数据的方法 
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

const int maxn = 5000;
int n, x[maxn], y[maxn];
ll dp[9][maxn];//后面有该数组的定义.

//注意这个函数的返回类型,是pair<int,int>.
//在这里可以理解为返回两个数分别是ordering(i,d).first和ordring(i,d).second
//主要用于之后的排序 
ii ordering(int i, int d) 
{
    if (d==0) return ii( y[i],  x[i]);
    if (d==2) return ii(-x[i],  y[i]);
    if (d==4) return ii(-y[i], -x[i]);
    if (d==6) return ii( x[i], -y[i]);

    if (d==1) return ii(-x[i] + y[i],  x[i] + y[i]);
    if (d==3) return ii(-x[i] - y[i], -x[i] + y[i]);
    if (d==5) return ii( x[i] - y[i], -x[i] - y[i]);
    if (d==7) return ii( x[i] + y[i],  x[i] - y[i]);
}

int main() {
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> x[i] >> y[i];
    }

    vector<int> order[8]; 
    for (int d=0; d<8; d++) {
        order[d] = vector<int>(n);
        for (int i=0; i<n; i++) {
            order[d][i] = i;
        }
        sort(begin(order[d]), end(order[d]), [&](int a, int b) -> bool { return ordering(a,d) < ordering(b,d);} );
        //按粒子运动方向进行排序 
        //[&](int a, int b) -> bool { return ordering(a,d) < ordering(b,d); 相当于自定义的排序函数函数,
        //在这里除了方便没什么别的用处. 
    }

    ll res = 0;
    for (int i=0; i<n; i++) //将每个点都作为起点查找一次 
    {
        for (int j=0; j<n; j++) // 初始化
        {
            dp[0][j] = 0;
        }
        dp[0][i] = 1; 
        //dp[d][j]表示粒子从i点出发使用了d条边到达j点的方案数.
        for(int d=0; d < 8; d++)//遍历8个方向,计算dp[ ][ ] 
        {
            int last = -1;
            for (int j : order[d])
            {
                if(last==-1)
                    dp[d+1][j]=0;
                if (ordering(j, d).first != ordering(last, d).first) 
                    dp[d+1][j]=0;
                else 
                    dp[d+1][j]=dp[d][last] + dp[d+1][last];
                last = j;
            }
        }
        //cout<<" "<<dp[8][i]<<endl; 
        res += dp[8][i];//使用了八条边后回到起点的方案数. 
    }
    cout<<res<<endl;
}

有错误欢迎指正.QAQ