dp cf 20190615

这个不算是dp，就是一个思维题，好难想的思维题，看了题解才写出来的，

把点和边分开，如果一条边的两个点颜色不同就是特殊边，特殊边两边连的点就叫特殊点，

如果一个点的被计算的次数等于特殊边的次数，则说明它是我们所求的点

#include <cstdio>

#include <cstdlib>

#include <queue>

#include <vector>

#include <cstring>

#include <algorithm>

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn = 1e5 + ;

int num[maxn], a[maxn];

pair<int, int>pii[maxn];

int main()

{

    int n;

    scanf("%d", &n);

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

    {

        int u, v;

        scanf("%d%d", &u, &v);

        pii[i] = make_pair(u, v);

    }

    int ans = ;

    for (int i = ; i <= n; i++) scanf("%d", &a[i]);

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

    {

        int u = pii[i].first, v = pii[i].second;

        if(a[u]!=a[v])

        {

            num[u]++;

            num[v]++;

            ans++;

        }

    }

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

    {

        if(num[i]==ans)

        {

            printf("YES\n");

            printf("%d\n",i);

            return ;

        }

    }

    printf("NO\n");

    return ;

}

A. Chain Reaction

这个我觉得挺难的。。。。

网上题解，dp[i]来表示激活第i个位置，从前面往后推到第i个位置，这个塔存留下来的数量。

这个是线性的，后面那个位置都是由前面的那个位置推过来的，如果我们选了后面那个位置，如果后面的无法把前面的那个位置炸掉

那么只能不炸，或者由最后添加的那个点来炸掉之前你需要炸掉的区间。

这个题目简单，是因为可以转化成线性的，不过我觉得好难想。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#define inf 0x3ff3f3f

using namespace std;

const int maxn = 1e6 + ;

int d[maxn], dp[maxn];

int main()

{

    int n;

    scanf("%d", &n);

    int mm = ;

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

    {

        int a;

        scanf("%d", &a);

        scanf("%d", &d[a]);

        mm = max(mm, a);

    }

    if (d[]) dp[] = ;

    int res = min(n, n - dp[]);

    for(int i=;i<=mm;i++)

    {

        if (d[i] == ) dp[i] = dp[i - ];

        else {

            if (d[i] >= i) dp[i] = ;

            else {

                dp[i] = dp[i -  - d[i]] + ;

            }

        }

        res = min(res, n - dp[i]);

    }

    printf("%d\n", res);

    return ;

}

巴特西

dp cf 20190615

最新文章

热门文章