Atcoder Regular 097 相邻球交换目的递增DP

/*Huyyt*/

#include<bits/stdc++.h>

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

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const ll LLmaxn = 2e18;

string a;

int K;

string str[];

int pop = ;

map<string, int> mp;

int main()

{

        cin >> a;

        cin >> K;

        for (int i = ; i <=  && pop < K; i++)

        {

                for (int j = ; j < a.size(); j++)

                {

                        if (a[j] == 'a' + i)

                        {

                                string now = "";

                                for (int k = j; k < min((int)a.size(), j + K); k++)

                                {

                                        now += a[k];

                                        if (!mp[now])

                                        {

                                                str[++pop] = now;

                                                //cout<<now<<endl;

                                                mp[now]++;

                                        }

                                }

                        }

                }

        }

        sort(str + , str + pop + );

        cout << str[K] << endl;

        return ;

}

给1-N的一个排列再给你M个Xi,Yi表示Xi与Yi位置的数可以无限次交换

解:

并查集因为交换次数是无线的所以在一个集内的数字可以到其他任何一个位置

/*Huyyt*/

#include<bits/stdc++.h>

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

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const ll LLmaxn = 2e18;

const int N = ;

int par[N];

void init(int n)

{

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

        {

                par[i] = i;

        }

}

int find(int x)

{

        return par[x] == x ? x : par[x] = find(par[x]);

}

void unite(int x, int y)

{

        x = find(x);

        y = find(y);

        if (x != y)

        {

                par[x] = y;

        }

}

int num[N];

int where[N];

int a, b;

int main()

{

        int n;

        int m;

        cin >> n;

        cin >> m;

        init(n);

        int anser = ;

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

        {

                cin >> num[i];

                where[num[i]] = i;

        }

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

        {

                cin >> a >> b;

                unite(a,b);

        }

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

        {

                if (find(where[i]) == find(i))

                {

                        anser++;

                }

        }

        cout << anser << endl;

        return ;

}

有2N个球一半是白的一半是黑的每个白球和黑球上都有一个数字分别都可以组成1-N

在一次操作内你可以交换相邻的两个球问你最少需要多少次操作使得从左到右白球和黑球各自都是递增序

解:

dp[i][j]表示现在在(i+j)的位置有1-i白球且1-j黑球正确排序所需要的最少操作数

pre[kind][i][j]表示第kind种的球在第i个位置及之前标号不小于j的有几个

/*Huyyt*/

#include<bits/stdc++.h>

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

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const ll LLmaxn = 2e18;

const int N = 2e3 + ;

int n;

int s;

int dp[N][N];

int pos[][N];

int pre[][N * ][N];

void init()

{

        for (int kind = ; kind <= ; kind++)

        {

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

                {

                        for (int j = n - ; j >= ; j--)

                        {

                                pre[kind][i][j - ] += pre[kind][i][j];

                        }

                }

                for (int i = ; i < s - ; i++)

                {

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

                        {

                                pre[kind][i + ][j] += pre[kind][i][j];

                        }

                }

        }

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

        {

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

                {

                        dp[i][j] = INT_MAX;

                }

        }

        dp[][] = ;

}

int main()

{

        cin >> n;

        s = n * ;

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

        {

                string ch;

                cin >> ch;

                int kind = ;

                int x;

                cin >> x;

                x--;

                if (ch[] == 'W')

                {

                        kind = ;

                }

                pos[kind][x] = i;

                pre[kind][i][x]++;

        }

        init();

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

        {

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

                {

                        if (i < n)

                        {

                                int p = pos[][i];

                                dp[i + ][j] = min(dp[i + ][j], dp[i][j] + pre[][p][i + ] + pre[][p][j]);

                        }

                        if (j < n)

                        {

                                int p = pos[][j];

                                dp[i][j + ] = min(dp[i][j + ], dp[i][j] + pre[][p][i] + pre[][p][j + ]);

                        }

                }

        }

        cout << dp[n][n] << endl;

        return ;

}

巴特西

Atcoder Regular 097 相邻球交换目的递增DP

最新文章

热门文章