头像

爱摸鱼的云玩家




离线:3天前



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

using namespace std;

const int N = 20010;
int f[N], g[N], q[N];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ )
    {
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        memcpy(g, f, sizeof f);
        for (int j = 0; j < v; j ++ )
        {
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += v)
            {
                if (hh <= tt && q[hh] < k - v * s) hh ++;
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt --;
                q[++ tt] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v * w;
            }
        }
    }
    printf("%d\n", f[m]);
    return 0;
}


活动打卡代码 AcWing 90. 64位整数乘法

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 110;
int a[N], b[N], n, c[N + N];
LL A, B, p;

void mul(int a[], int b[])
{
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            c[i + j] += (a[i] * b[j]) % p;
    LL res = 0;
    for (int i = 2 * n; i >= 0; i -- )
        res = (res * 10 + c[i]) % p;
    res %= p;
    printf("%lld\n", res);
}

int main()
{
    scanf("%lld%lld%lld", &A, &B, &p);
    int i = 0;
    while (A)
    {
        a[i] = A % 10;
        A /= 10;
        i ++;
    }
    n = i;
    i = 0;
    while (B)
    {
        b[i] = B % 10;
        B /= 10;
        i ++;
    }
    n = max(n, i);
    mul(a, b);
    return 0;
}


活动打卡代码 AcWing 1323. 出现

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

bool st[N];
int n;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int x;
        scanf("%d", &x);
        st[x] = true;
    }
    for (int i = 0; i < 1001; i ++ )
    {
        if (!st[i])
        {
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}


活动打卡代码 AcWing 89. a^b

#include <iostream>
#include <algorithm>

using namespace std;

long long a, b, p;

int main()
{
    scanf("%lld%lld%lld", &a, &b, &p);
    long long res = 1;
    for (int i = 0; i < 31; i ++ )
    {
        if ((b >> i) & 1) res = (res * a) % p;
        a = (a * a) % p;
    }
    res %= p;
    printf("%lld\n", res);
}



#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3010;

int f[N][N], a[N], b[N];
int 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 - 1][j] + 1);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i ++ )  
        res = max(res, f[n][i]);
    printf("%d\n", res);

    return 0;
}


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

k 不能定义成全局变量,否则还原现场的时候,因为是全局变量,并不能正确的还原!!!!!

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 55;

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

void dfs(int u, int su, int sd)
{
    if (su + sd >= ans) return;
    if (u == n)
    {
        ans = su + sd;
        return;
    }
    //up
    int k = 0;
    while (k < su && up[k] > a[u]) k ++;
    if (k < su)
    {
        int t = up[k];
        up[k] = a[u];
        dfs(u + 1, su, sd);
        up[k] = t;
    }
    else 
    {
        up[k] = a[u];
        dfs(u + 1, su + 1, sd);
    }
    //down
    k = 0;
    while (k < sd && down[k] < a[u]) k ++;
    if (k < sd)
    {
        int t = down[k];
        down[k] = a[u];
        dfs(u + 1, su, sd);
        down[k] = t;
    }
    else 
    {
        down[k] = a[u];
        dfs(u + 1, su, sd + 1);
    }
}

int main()
{
    while (scanf("%d", &n) != EOF, n)
    {
        for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

        ans = n;
        dfs(0, 0, 0);
        printf("%d\n", ans);
    }
    return 0;
}
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 55;
int up[N], down[N], a[N];
int n;

bool dfs(int depth, int u, int su, int sd)
{
    if (su + sd > depth) return false;
    if (u == n) return true;
    int k = 0;
    while (k < su && up[k] > a[u]) k ++;
    if (k < su)
    {
        int t = up[k];
        up[k] = a[u];
        if (dfs(depth, u + 1, su, sd)) return true;
        up[k] = t;
    }
    else
    {
        up[k] = a[u];
        if (dfs(depth, u + 1, su + 1, sd)) return true;
    }
    k = 0;
    while (k < sd && down[k] < a[u]) k ++;
    if (k < sd)
    {
        int t = down[k];
        down[k] = a[u];
        if (dfs(depth, u + 1, su, sd)) return true;
        down[k] = t;
    }
    else
    {
        down[k] = a[u];
        if (dfs(depth, u + 1, su, sd + 1)) return true;
    }
    return false;
}

int main()
{
    while (scanf("%d", &n) != EOF, n)
    {
        for (int i = 0; i < n; i ++ ) scanf("%d", a + i);

        int depth = 0;
        while (!dfs(depth, 0, 0, 0)) depth ++;
        printf("%d\n", depth);
    }
    return 0;
}



题目链接 https://www.acwing.com/problem/content/189/

为什么k定义成全局变量就不可以了啊?明明每次都初始化为0了

错误的代码:

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 55;
int a[N], up[N], down[N];
int ans;
int n;
int k;

void dfs(int u, int us, int ud)
{
    if (us + ud >= ans) return;
    if (u == n)
    {
        printf("%d, %d\n", us, ud);
        ans = us + ud;
        return;
    }
    //up
    // int k = 0;
    k = 0;
    while (k < us && up[k] > a[u]) k ++;
    if (k < us)
    {
        int t = up[k];
        up[k] = a[u];
        dfs(u + 1, us, ud);
        up[k] = t;
    }
    else 
    {
        up[k] = a[u];
        dfs(u + 1, us + 1, ud);
    }
    //down
    k = 0;
    while (k < ud && down[k] < a[u]) k ++;
    if (k < ud)
    {
        int t = down[k];
        down[k] = a[u];
        dfs(u + 1, us, ud);
        down[k] = t;
    }
    else 
    {
        down[k] = a[u];
        dfs(u + 1, us, ud + 1);
    }
}

int main()
{
    while (scanf("%d", &n) != EOF, n)
    {
        for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

        ans = n;
        dfs(0, 0, 0);
        printf("%d\n", ans);
    }
    return 0;
}

WA了



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

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    while (scanf("%d", &a[n]) != EOF) n ++;
    for (int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++ )
            if (a[j] >= a[i]) f[i] = max(f[i], f[j] + 1);
    }
    int res = 0;
    for (int i = 0; i < n; i ++ )
        res = max(res, f[i]);
    printf("%d\n", res);

    int len = 0;
    for (int i = 0; i < n; i ++ )
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }
    printf("%d\n", len);
    return 0;
}



#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int f[N], a[N];
int n;

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

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

    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]);
    }
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        res = max(res, f[i]);

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


活动打卡代码 AcWing 1012. 友好城市

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;
const int N = 5010;

PII a[N];
int f[N], q[N];
int n;

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

    sort(a + 1, a + n + 1);

    int len = 0;
    q[0] = -2e9;
    for (int i = 1; i <= n; i ++ )
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i].second) l = mid;
            else  r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i].second;
    }
    printf("%d\n", len);
    return 0;
}