题解 P6269 【[SHOI2002]空中都市】

· · 题解

此题题意非常简单，就是画一个有N个结点的图，使得图中不存在一个含有三个点的子图，问最多可以有多少条边。

很显然，当N<3时答案肯定是N-1，因为当N=3时不管怎么架桥都必须要拆一座。

那？之后呢？

我们可以很容易地发现，对于每一个N，连的边数一定是N-1的边数+i/2,即 对于每一个i

f[i]=f[i-1]+i/2

为什么呢？

很简单，因为假设我们多连一条边，那么一定会有一条冗余的一条边。我们可以假设N个点组成的N-1组成的那个图，那么会有一个孤点，我们可以将这个点连若干条边，可以顺次连，当我们连到N/2+1时就会组成三角形 1->N/2->N/2+1,这个很简单，泥萌应该都知道吧。

之后，就是代码啦：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int f[10005];
    f[0]=0;//初始一下
    for(int i=1;i<=n;i++)
    f[i]=f[i-1]+(i/2);//套上面的公式，相当于一个小递推
    cout<<f[n];//输出第N个
    return 0;
}

于是你就AC了一道远古时代的被恶评的省选题