个人空间 - AcWing

神魔皆以血嗜

阅读量

7237

+关注发消息

在线

最近来访(131)

忍_7

xyd

顽童

むぎわらボイス

NinjaNB

WA高手胡先生

Ning0-0

Somewhere_1

lfh

DraymoNd_

cjh2023

GGBoy-

哥屋嗯.

wsxzq

_Sakura_

eswzy

acwing_06648

胡尔摩斯

秋天深了

Detach..

活动打卡代码 AcWing 272. 最长公共上升子序列

神魔皆以血嗜
1小时前

                #include <iostream>
#include <algorithm>

using namespace std;

const int N = 3010;

int n;
int a[N], b[N];
int f[N][N];

int main()
{
    scanf("%d", &n);

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

    for (int i = 1; i <= n; i ++ )
    {
        int maxv = 1;
        for (int j = 1; j <= n; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
            if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);

    printf("%d", res);

    return 0;
}

            

活动打卡代码 AcWing 272. 最长公共上升子序列

神魔皆以血嗜
19小时前

                $O(n^3)$超时
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3010;

int n;
int a[N], b[N];
int f[N][N];

int main()
{
    scanf("%d", &n);

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

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j])
            {
                f[i][j] = max(f[i][j], 1);
                for (int k = 1; k < j; k ++ )
                    if (b[k] < b[j])
                        f[i][j] = max(f[i][j], f[i][k] + 1);
            }
        }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);

    printf("%d", res);

    return 0;
}


$O(n^2)偷懒写法$
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3010;

int n;
int a[N], b[N];
int f[N][N];

int main()
{
    scanf("%d", &n);

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

    for (int i = 1; i <= n; i ++ )
    {
        int maxv = 1;
        for (int j = 1; j <= n; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j])
                f[i][j] = max(f[i][j], maxv);

            if (b[j] < a[i]) maxv = max(maxv, f[i][j] + 1);
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);

    printf("%d", res);

    return 0;
}


不偷懒写法（超内存）
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3001;

int n;
int a[N], b[N];
int g[N][N]; // g[i][j]表示满足a[i] > b[j] 的所有 f[i][j] + 1 的最大值
int f[N][N];

int main()
{
    scanf("%d", &n);

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

    for (int i = 1; i <= n; i ++ )
    {
        g[i][0] = 1;
        for (int j = 1; j <= n; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j])
                f[i][j] = max(f[i][j], g[i][j - 1]);
            g[i][j] = g[i][j - 1];
            if (b[j] < a[i]) g[i][j] = max(g[i][j], f[i][j] + 1);
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);

    printf("%d", res);

    return 0;
}

            

活动打卡代码 AcWing 187. 导弹防御系统

神魔皆以血嗜
19小时前

                #include <iostream>
#include <algorithm>

using namespace std;

const int N = 55;

int n;
int q[N];
int up[N], down[N];
int ans;

void dfs(int u, int su, int sd)
{
    if (su + sd >= ans) return;
    if (u == n)
    {
        ans = su + sd;
        return;
    }

    //情况1
    int k = 0;
    while (k < su && up[k] >= q[u]) k ++;
    int t = up[k];
    up[k] = q[u];
    if (k < su) dfs(u + 1, su, sd);
    else dfs(u + 1, su + 1, sd);
    up[k] = t;

    //情况2
    k = 0;
    while (k < sd && down[k] <= q[u]) k ++;
    t = down[k];
    down[k] = q[u];
    if (k < sd) dfs(u + 1, su, sd);
    else dfs(u + 1, su, sd + 1);
    down[k] = t;
}

int main()
{
    while (cin >> n, n)
    {
        for (int i = 0; i < n; i ++ ) cin >> q[i];

        ans = n;

        dfs(0, 0, 0);

        cout << ans << endl;
    }

    return 0;
}

            

活动打卡代码 AcWing 1010. 拦截导弹

神魔皆以血嗜
20小时前

                #include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int q[N];
int f[N], g[N];

int main()
{
    while (cin >> q[n]) n ++;

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++ )
            if (q[j] >= q[i])
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }

    cout << res << endl;

    int cnt = 0;
    for (int i = 0; i < n; i ++ )
    {
        int k = 0;
        while (k < cnt && g[k] < q[i]) k ++;
        g[k] = q[i];
        if (k >= cnt) cnt ++;
    }

    cout << cnt << endl;

    return 0;
}

            

活动打卡代码 AcWing 271. 杨老师的照相排列

神魔皆以血嗜
20小时前

                #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 31;

int n;
LL f[N][N][N][N][N];

int main()
{
    while (cin >> n, n)
    {
        int s[5] = {0};
        for (int i = 0; i < n; i ++ ) scanf("%d", &s[i]);

        memset(f, 0, sizeof f);
        f[0][0][0][0][0] = 1;
        for (int a = 0; a <= s[0]; a ++ )
            for (int b = 0; b <= min(a, s[1]); b ++ )
                for (int c = 0; c <= min(b, s[2]); c ++ )
                    for (int d = 0; d <= min(c, s[3]); d ++ )
                        for (int e = 0; e <= min(d, s[4]); e ++ )
                        {
                            LL &v = f[a][b][c][d][e];
                            if (a && a - 1 >= b) v += f[a - 1][b][c][d][e];
                            if (b && b - 1 >= c) v += f[a][b - 1][c][d][e];
                            if (c && c - 1 >= d) v += f[a][b][c - 1][d][e];
                            if (d && d - 1 >= e) v += f[a][b][c][d - 1][e];
                            if (e) v += f[a][b][c][d][e - 1];
                        }

        printf("%lld\n", f[s[0]][s[1]][s[2]][s[3]][s[4]]);
    }

    return 0;
}

            

活动打卡代码 AcWing 285. 没有上司的舞会（算法基础课）

神魔皆以血嗜
2天前

                #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 6010;

int n;
int happy[N];
int f[N][2];
bool has_father[N];
int h[N], e[N], ne[N], idx;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u)
{
    f[u][1] = happy[u];

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

int main()
{
    scanf("%d", &n);

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

    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, a);
        has_father[a] = true;
    }

    int root = 1;
    while (has_father[root]) root ++;

    dfs(root);

    printf("%d", max(f[root][0], f[root][1]));

    return 0;
}

            

活动打卡代码 AcWing 4550. 超级跳跳跳

神魔皆以血嗜
3天前

                #include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N];
int f[N];

int main()
{
    while (cin >> n, n)
    {
        for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

        int res = 0;
        for (int i = 1; i <= n; i ++ )
        {
            f[i] = a[i];
            for (int j = 1; j < i; j ++ )
                if (a[j] < a[i])
                    f[i] = max(f[i], f[j] + a[i]);
            res = max(res, f[i]);
        }

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

    return 0;
}

            

活动打卡代码 AcWing 4555. 公共子序列

神魔皆以血嗜
3天前

                #include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010;

char a[N], b[N];
int f[N][N];

int main()
{
    while (cin >> a + 1 >> b + 1)
    {
        int n = strlen(a + 1), m = strlen(b + 1);
        if (!strcmp(a + 1, b + 1))
        {
            printf("%d\n", n);
            continue;
        }
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
            {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
            }

        printf("%d\n", f[n][m]);
    }

    return 0;
}

            

活动打卡代码 AcWing 4547. 伊格内修斯和公主IV

神魔皆以血嗜
3天前

                直接暴力卡过去
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1000010;

int n;
int a[N];
int s[N];

int main()
{
    while (cin >> n)
    {
        memset(s, 0, sizeof s);
        int ans = (n + 1) / 2;
        bool flag = true;
        for (int i = 0; i < n; i ++ )
        {
            scanf("%d", &a[i]);
            if (flag) 
            {
                s[a[i]] ++;
                if (s[a[i]] >= ans)
                {
                    printf("%d\n", a[i]);
                    flag = false;
                }
            }
        }
    }

    return 0;
}

            

活动打卡代码 AcWing 4557. 最长上升子序列

神魔皆以血嗜
3天前

                #include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N];
int f[N];

int main()
{
    scanf("%d", &n);

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

    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        f[i] = 1;
        for (int j = 1; j < i; j ++ )
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }

    printf("%d", res);

    return 0;
}

            