Gym - 101964I

题意

有一个数组\(p\)，如果满足\(i<j,p_i>p_j\),则\(i,j\)之间就有一条边相连，问存在多少个集合满足集合内的元素互不相连，且集合外的元素都有边连到集合内。

思路

现在给你\(p\)数组相连的边，然后就可以暴力还原\(p\)数组，可以先记录有当前\(i\)位置之小于\(i\)位置的数字的数数量\(k\)，然后从小到大找能用的第\(k\)大的数字就是位置\(i\)的数字

还原完\(p\)数组，我们可以发现如果你的子序列是上升序列，那么它们直接互不相连，而要让其他元素都连到这个集合里，我们要找不可扩展的上升序列（就是后面没有更大的数字，前面没有更小的数字），然后就会发现剩下的元素就会连到集合内，不然就会被加集合内

所以，这题就是还原\(p\)数组，然后找到不可扩展的上升序列有多少个，就是答案了。

代码

#include<bits/stdc++.h>

#define mes(a, b) memset(a, b, sizeof a)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxm = 1e6+10;

const int maxn = 1e5+10;

int n, m, T;

int a[maxn], in[maxn], vis[maxn];

ll ans, dp[maxn];

int main(){

    scanf("%d%d", &n, &m);

    int x, y;

    for(int i = 1; i <= m;i++){

        scanf("%d%d", &x, &y);

        in[min(x, y)]++;

    }

    for(int i = 1; i <= n; i++){

        for(int j = 1; j <= n; j++){

            if(!vis[j]){

                if(in[i]) in[i]--;

                else{

                    vis[j] = 1;

                    a[i] = j;

                    break;

                }

            }

        }

    }

    for(int i = 1; i <= n; i++){

        int Max = 0;

        for(int j = i-1; j >= 1; j--){

            if(a[i] > a[j] && a[j] > Max){ 	//如果当前a[j]比Max小，那么肯定a[j]有被Max的数更新过，就不要更新了

                Max = a[j];

                dp[i] += dp[j];

                in[j]++;

            }

        }

        if(!dp[i])

            dp[i] = 1;

    }

    ans = 0;

    for(int i = 1; i <= n; i++){

        if(!in[i])

            ans += dp[i];

    }

    printf("%lld\n", ans);

    return 0;

}

巴特西

SEERC 2018 I - Inversion (Gym - 101964I) DP

Gym - 101964I

题意

思路

代码

最新文章

热门文章