头像

浅幽丶奈芙莲




离线:5小时前


最近来访(14)
用户头像
wmh123
用户头像
acwing9876
用户头像
清清小苏打
用户头像
ACALL139
用户头像
夢桜雪
用户头像
acwing_1914
用户头像
ForwardForever
用户头像
CVer
用户头像
Catw1thu
用户头像
acgangster
用户头像
dp_5
用户头像
最后一只三脚兽
用户头像
tonpirdrea

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

#include <iostream>

using namespace std;

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

int main() {
    cin >> n >> a >> m >> b;
    a = " " + a;
    b = " " + b;

    for (int i = 1; i <= n; i++) f[i][0] = i;
    for (int i = 1; i <= m; i++) f[0][i] = i;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            // f[i][j] a的1~i子串变成b的1~j子串,至少需要进行的次数
            // 最后一步是增加最后一个字母 | 最后一步是删除最后一个字母 | 最后一步是修改最后一个字母
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }
    cout << f[n][m];
}



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

#include <iostream>

using namespace std;

const int N = 1010, M = 1e9 + 7;
int n, f[N][N] ;

int main() {
    cin >> n;

    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n; j++) {
            f[i][j] = f[i - 1][j];
            if (j - i >= 0)
                f[i][j] = (f[i][j] + f[i][j - i]) % M;
        }
    cout << f[n][n];
}



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

#include <iostream>
#include <cstring>

using namespace std;

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

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

    memset(f, 0x3f, sizeof f);
    for (int l = 0; l < n; l++)
        for (int i = 1; i + l <= n; i++) {
            if (l == 0) {
                f[i][i] = 0;
                continue;
            }
            int j = i + l;
            for (int k = i; k < j; k++)
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + a[j] - a[i - 1]);
        }
    cout << f[1][n];
}



活动打卡代码 AcWing 5. 多重背包问题 II

#include<iostream>

using namespace std;

const int N = 12010, M = 2010;

int n, m, v[N], w[N], f[M];

int main() {
    cin >> n >> m;
    int cnt = 0;  // 将n种物品打包成cnt个组,每组是一个选择方案
    for (int i = 1; i <= n; i++) {
        int a, b, s;
        cin >> a >> b >> s;
        for (int k = 1; k <= s; k *= 2) {  // 分别打包成1、2、4……个位一组
            cnt++;  // 组别先增加
            v[cnt] = a * k;  // 该打包组的体积
            w[cnt] = b * k;  // 该打包组的价值
            s -= k;  // s要减小
        }
        if (s > 0) {  // 剩余的一组
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    // 枚举次数n由个数变成组数。多重背包转为01背包
    for (int i = 1; i <= cnt; i++)
        for (int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m];
}



活动打卡代码 AcWing 125. 耍杂技的牛

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50010;
int n, sum, ans = -0x3f3f3f3f;
pair<int, int> a[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int w, s;
        cin >> w >> s;
        a[i] = {w + s, w};
    }
    sort(a, a + n);
    for (int i = 0; i < n; i++) {
        int w = a[i].second, s = a[i].first - a[i].second;
        ans = max(ans, sum - s);
        sum += w;
    }
    cout << ans;
}



活动打卡代码 AcWing 104. 货仓选址

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, a[N];
long long ans;

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

    for (int i = 0; i < n; i++) ans += abs(a[i] - a[n / 2]);
    cout << ans;
}



活动打卡代码 AcWing 913. 排队打水

#include <iostream>
#include <queue>

using namespace std;

const int N = 100010;
int n;
long long ans;
priority_queue<int, vector<int>, greater<>> heap;

int main() {
    cin >> n;
    for (int i = 0, t; i < n; i++) {
        cin >> t;
        heap.push(t);
    }

    while (!heap.empty()) {
        ans += heap.top() * (heap.size() - 1);
        heap.pop();
    }
    cout << ans;
}



活动打卡代码 AcWing 148. 合并果子

#include <iostream>
#include <queue>

using namespace std;

const int N = 10010;
int n, res;
priority_queue<int, vector<int>, greater<>> heap;

int main() {
    cin >> n;
    for (int i = 0, t; i < n; i++) {
        cin >> t;
        heap.push(t);
    }

    while (!heap.empty()) {
        int c = heap.top();
        heap.pop();
        if (heap.empty()) break;
        c += heap.top();
        heap.pop();
        heap.push(c);
        res += c;
    }

    cout << res;
}



活动打卡代码 AcWing 907. 区间覆盖

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, st, ed, res;
pair<int, int> a[N];
bool succ;

int main() {
    cin >> st >> ed >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i].first >> a[i].second;

    sort(a, a + n);
    for (int i = 0; i < n;) {
        int j = i, r = -2e9;  // j为候选区间,r是最右边界
        while (j < n && a[j].first <= st) {  // 还有区间并且能覆盖目标左边界
            r = max(r, a[j].second);  // 找最右边界
            j++;
        }
        if (r < st) break;
        res++;
        if (r >= ed) {
            succ = true;
            break;
        }
        i = j;
        st = r;
    }
    if (!succ) res = -1;
    cout << res;
}



活动打卡代码 AcWing 906. 区间分组

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
const int N = 100010;
int n;
PII a[N];
priority_queue<int, vector<int>, greater<>> heap;  // !注意堆的语法

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;

    sort(a, a + n);

    for (int i = 0; i < n; i++) {
        int l = a[i].first, r = a[i].second;
        if (heap.empty() || l <= heap.top())
            ;
        else
            heap.pop();
        heap.push(r);
    }
    cout << heap.size();
}