E - Node Pairs

题意

题意晦涩难懂，但理解了之后就发现是让计算两个值：

1.最小的n使得一个具有n个点的图上两两连通的点的对数恰好为p

2.在满足1的条件的图中，求最大的两两不连通的点的对数

思路

对于第一问，考虑到一个事实，对于有连通的x个点来讲，最大化其两两连通的点对数的情况是，这x个点都互相两两联通（形成一个环），如果有一个点跟这x个点中的任何一个点互相连通，那么这x个点中的其他x-1个点也会跟这个点互相连通。所以第1问就是让求满足\(\sum\frac{x_i(x_i-1)}{2}=p\)的最小的\(\sum{x_i}\)。

对于第二问，实际上就是在每个块都形成环的情况下，不同的连通块间没有任何连边的情况，答案即为\(\prod{x_i}\)

用动态规划，很容易得到状态转移方程\(dp[i]=min(dp[i-\frac{j(j-1)}{2}]+j)\)，再用一个vector数组维护每个i对应的连通块中点的个数的情况即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define LL long long

const int maxn = 2e5 + 5, maxnn = 1e9 + 7;

vector<int> ans[maxn];
int a[maxn], g = 1, b[maxn];

void sol() {
    int p;
    cin >> p;
    for (int i = 1; i <= p; ++i) {
        b[i] = maxnn;
        for (int j = 2; 1ll * j * (j - 1) / 2 <= i; ++j) {
            int idx = i - 1ll * j * (j - 1) / 2;
            if (b[idx] + j < b[i]) {
                ans[i] = ans[idx];
                ans[i].push_back(j);
                b[i] = b[idx] + j;
            }
        }
    }
    cout << b[p] << ' ';
    int x = ans[p].size();
    if (x == 0 || x == 1) {
        cout << 0 << endl;
        return;
    }
    LL sum = 0, tmp = 0;
    for (vector<int>::iterator i = ans[p].end() - 1; i != ans[p].begin() - 1;
         --i) {
        sum += *i * tmp;
        tmp += *i;
    }
    cout << sum << endl;
}

int main() {
    sol();
    return 0;
}