头像

StarLi9ht




离线:9小时前


最近来访(67)
用户头像
目标不检测
用户头像
用户头像
一万小时定律
用户头像
小火龙
用户头像
赛博丁真会梦到电子烟吗
用户头像
雷克喵
用户头像
Sherlock_0
用户头像
arch_hui
用户头像
笑脸人
用户头像
Eaf_quakee
用户头像
Shmilysw
用户头像
嘤嘤嘤_1
用户头像
yxc
用户头像
執念_8
用户头像
XX31MRK
用户头像
南笙离梦
用户头像
千岁朔
用户头像
Atopos_
用户头像
顽童
用户头像
GeekAlice

活动打卡代码 AcWing 900. 整数划分

StarLi9ht
12小时前

1.完全背包写法

1660301890857.png

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N];

int main() 
{
    cin >> n;

    f[0] = 1;

    for (int i = 1; i <= n; i ++)
        for (int j = i; j <= n; j ++)
            f[j] = (f[j] + f[j - i]) % mod;

    cout << f[n] << endl;

    return 0;
}

2.另一种算法

1660303667204.png

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

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

int main() 
{
    cin >> n;

    f[1][1] = 1;

    for (int i = 2; i <= n; i ++)
        for (int j = 1; j <= i; j ++)
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;

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

    cout << res << endl;

    return 0;
}



StarLi9ht
17小时前

我一开始的想法是把f数组全部初始化为INF

memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= m; i ++) f[0][i] = i;
for (int i = 1; i <= n; i ++) f[i][0] = i;

发现这样是错的,因为状态计算的过程会用到f[0][0],而f[0][0]应该等于0,所以这样就对了

memset(f, 0x3f, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= m; i ++) f[0][i] = i;
for (int i = 1; i <= n; i ++) f[i][0] = i;

这样初始化符和我最开始的想法,就是某次状态计算可能会使用到无法到达的状态,即 f[?][?] = INF

转念一想,其实状态计算过程中,ij都是从小到大遍历的,所以状态计算用到的状态一定是已经被计算过的,或者上述初始化中的状态


所以只需要这样初始化就可以了

for (int i = 1; i <= m; i ++) f[0][i] = i;
for (int i = 1; i <= n; i ++) f[i][0] = i;


活动打卡代码 AcWing 899. 编辑距离

StarLi9ht
18小时前
#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 20;

int n, m;
char a[N][M], b[M];
int f[M][M];

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

    while (m --) {
        int t;
        scanf("%s%d", b + 1, &t);
        int m1 = strlen(b + 1);

        int res = 0;
        for (int k = 0; k < n; k ++)
        {
            int n1 = strlen(a[k] + 1);

            for (int i = 1; i <= m1; i ++) f[0][i] = i;
            for (int i = 1; i <= n1; i ++) f[i][0] = i;

            for (int i = 1; i <= n1; i ++)
                for (int j = 1; j <= m1; j ++)
                {
                    f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                    if (a[k][i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
                    else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
                }

            if (f[n1][m1] <= t) res ++;
        }

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

    return 0;
}


活动打卡代码 AcWing 902. 最短编辑距离

StarLi9ht
18小时前

Screenshot 2022-08-12 132215.jpg


#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010;

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

int main() {
    scanf("%d%s", &n, a + 1);
    scanf("%d%s", &m, b + 1);

    for (int i = 1; i <= m; i ++) f[0][i] = i;
    for (int i = 1; i <= n; i ++) f[i][0] = i;

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

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

    return 0;
}



StarLi9ht
20小时前



#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1000010;

int n;
int a[N];
int q[N];  // q[i] 表示 长度为i的最长上升子序列 的末尾最小值

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

    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;
}


活动打卡代码 AcWing 282. 石子合并

Screenshot 2022-08-10 215506.jpg

Screenshot 2022-08-10 215541.jpg

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 310;

int n;
int s[N];
int f[N][N];

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

    for (int i = 1; i <= n; i ++) s[i] += s[i - 1];

    for (int len = 2; len <= n; len ++)
        for (int i = 1; i + len - 1 <= n; i ++)
        {
            int l = i, r = i + len - 1;
            f[l][r] = 1e9;
            for (int k = l; k < r; k ++)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }

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

    return 0;
}



用1和0分别表示选或不选a[i]和b[j]

Screenshot 2022-08-10 212549.jpg


注意!!!

  1. f[i-1][j] 不等价于 01 这种情况,但 f[i-1][j]是包含 01 这种情况的,由于本题是求最大值,所以集合划分可以重复

  2. 由于 f[i-1][j-1] 既包含于 f[i-1][j] ,又包含于 f[i][j-1],所以f[i-1][j-1]可以省略

  3. 只有当a[i] == b[j]时,才可以考虑 11这种情况


#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010;

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

int main() {
    scanf("%d%d", &n, &m);
    scanf("%s%s", a + 1, b + 1);

    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;
}



Screenshot 2022-08-10 203711.jpg

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010;

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

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    for (int i = 1; i <= n; i ++) 
    {
        f[i] = 1; //只有a[i]一个数
        for (int j = 1; j < i; j ++)
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }

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

    cout << res << endl;

    return 0;
}

可以通过记录状态转移 来记录最佳方案

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 1010;

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

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    for (int i = 1; i <= n; i ++) 
    {
        f[i] = 1; //只有a[i]一个数
        for (int j = 1; j < i; j ++)
            if (a[j] < a[i])
                if (f[i] < f[j] + 1)
                {
                    f[i] = f[j] + 1;
                    g[i] = j;
                }

    }

    int k = 0;
    for (int i = 1; i <= n; i ++)
        if (f[k] < f[i])
            k = i;

    cout << f[k] << endl;

    for (int i = 0, len = f[k]; i < len; i ++)
    {
        cout << a[k] << ' ';
        k = g[k];
    }

    return 0;
}


活动打卡代码 AcWing 898. 数字三角形

Screenshot 2022-08-10 201649.jpg


#include <cstdio>
#include <iostream>

using namespace std;

const int N = 510, INF = 1e9;

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

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

    for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= i + 1; j ++)
            f[i][j] = -INF;

    f[1][1] = a[1][1];
    for (int i = 2; i <= n; i ++)
        for (int j = 1; j <= i; j ++)
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);

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

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

    return 0;
}