原题链接：

分析：先考虑不受限制的情况，此时共可以修n*(n-1)/2条隧道；所有的place组成一个多边形，多边形内部的三角形共有n*(n-1)/2个，考虑限制条件，那么每两个相邻的三角形组成的四边形的对角线应该删除，共ceiling[n*(n-2)/4]条边；所以答案就是n*n/4.

另解：dp[i]=i*(i-1)/2-dp[i-1];理解：i*(i-1)/2=i+（i-1）*（i-2)/2,那么(i-1)*(i-2)/2-dp[i-1]就表示前一个不满足限制条件的个数，当增加一个点时，就可以通过增加一条边来使其满足限制条件。

Tunnel

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 int main() 6 { 7     int T;long long n; 8     scanf("%d",&T); 9     while(T--)10     {11         scanf("%lld",&n);long long ans;12         ans=n*n/4;13         printf("%lld\n",ans);14     }15     return 0;16 }