头像

limcc




离线:8天前


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

limcc
13天前
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510;
int n;
int w[N][N], f[N][N];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= i; j ++)
            cin >> w[i][j];
    }
    for (int i = 1; i <= n; i ++)
        f[n][i] = w[n][i];
    for (int i = n - 1; i; i --)
    {
        for (int j = 1; j <= i; j ++)
        {
            f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + w[i][j];
        }
    }
    cout << f[1][1];
    return 0;
}


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

limcc
17天前
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++)
        cin >> a[i];
    sort(a, a + n);
    long long res = 0;
    for (int i = 0; i < n; i ++)
        res += abs(a[n / 2] - a[i]);
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 1015. 摘花生

limcc
2个月前
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 110;
int f[N][N], w[N][N];
int n, m;
int main()
{
    int T;
    scanf("%d", &T);
    while (T --)
    {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < m; j ++)
            {
                f[i][j] = 0;
                scanf("%d", &w[i][j]);
            }
        int sum = 0;
        for (int i = 0; i < n; i ++) sum += w[i][0], f[i][0] = sum;
        sum = 0;
        for (int j = 0; j < m; j ++) sum += w[0][j], f[0][j] = sum;
        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]) + w[i][j];
        printf("%d\n", f[n - 1][m - 1]);
    }
    return 0;
}


活动打卡代码 AcWing 786. 第k个数

limcc
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n, k;
int quicksort(int a[], int l, int r, int k)
{
    if (l >= r) return a[l];
    int i = l - 1, j = r + 1;
    int x = a[l + r >> 1];
    while (i < j)
    {
        do i ++; while (a[i] < x);
        do j --; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    int sl = j - l + 1;
    if (k <= sl) return quicksort(a, l, j, k);
    return quicksort(a, j + 1, r, k - sl);  // 注意这里
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
    printf("%d\n", quicksort(a, 0, n - 1, k));
    return 0;
}


活动打卡代码 AcWing 901. 滑雪

limcc
5个月前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 310;
int r, c;
int f[N][N], a[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int dp(int x, int y)
{
    if (f[x][y] != -1) return f[x][y];
    f[x][y] = 1;  // 务必注意初始化,只走当前这格
    for (int i = 0; i < 4; i ++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 1 && nx <= r && ny >= 1 && ny <= c && a[nx][ny] < a[x][y])
        {
            f[x][y] = max(f[x][y], dp(nx, ny) + 1);
        }
    }
    return f[x][y];
}
int main()
{
    scanf("%d%d", &r, &c);
    int res = 0;
    for (int i = 1; i <= r; i ++)
    {
        for (int j = 1; j <= c; j ++)
            scanf("%d", &a[i][j]);
    }
    memset(f, -1, sizeof f);
    for (int i = 1; i <= r; i ++)
    {
        for (int j = 1; j <= c; j ++)
            res = max(res, dp(i, j));
    }
    printf("%d\n", res);
    return 0;
}



limcc
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 6010;
int h[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
bool has_fa[N];
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    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()
{
    memset(h, -1, sizeof h);
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%d", &happy[i]);
    for (int i = 0; i < n - 1; ++ i)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, a);
        has_fa[a] = true;
    }
    int root = 1;
    while (has_fa[root]) root ++;
    dfs(root);
    printf("%d\n", max(f[root][0], f[root][1]));
    return 0;
}码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

limcc
5个月前
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1010, mod = 1e9 + 7;
ll f[N][N];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i <= n; ++ i) f[i][0] = 1;  // 从1-i中选,和为0,只能全部都不选这一种选法
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= n; ++ j)
        {
            f[i][j] = (f[i][j] + f[i - 1][j]) % mod;
            if (j >= i) f[i][j] = (f[i][j] + f[i][j - i]) % mod;
        }
    }
    printf("%d\n", f[n][n]);
    return 0;
}


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

limcc
5个月前
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50010;
typedef pair<int, int> PII;
typedef long long ll;
PII cow[N];  // 存储s+w, w
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i)
    {
        int w, s;
        scanf("%d%d", &w, &s);
        cow[i] = {w + s, s};  // 存储w+s和s
    }
    sort(cow, cow + n);
    int res = -2e9, sum = 0;
    for (int i = 0; i < n; ++ i)
    {
        int s = cow[i].second, w = cow[i].first - s;
        res = max(res, sum - s);
        sum += w;
    }
    printf("%d\n", res);
    return 0;
}


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

limcc
5个月前
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;
struct Range
{
    int l, r;
    bool operator < (const Range &w)const
    {
        return l < w.l;
    }
}range[N];
int main()
{
    int st, ed;
    scanf("%d%d", &st, &ed);
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }
    sort(range, range + n);
    bool success = false;  // 标记是否成功
    int res = 0;
    for (int i = 0; i < n; ++ i)
    {
        int j = i, max_r = -2e9;  //记录能覆盖左端点的区间的最大右端点
        while (j < n && range[j].l <= st)
        {
            max_r = max(range[j].r, max_r);  // 找到区间的最大右端点
            j ++;
        }
        if (max_r < st)  // 最大右端点都比木棒的左端点小,说明没有区间能覆盖
        {
            res = -1;
            break;
        }
        res ++;  // 可以覆盖
        if (max_r >= ed)  // 最大右端点已经可以覆盖木棒右端点,结束
        {
            success = true;
            break;
        }
        st = max_r;  // 木棒左端点更新成最大右端点
        i = j - 1;  // 注意这里,后面++i的时候才会变成j
    }
    if (!success) printf("%d\n", -1);
    else printf("%d\n", res);
    return 0;
}


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

limcc
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
int a[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++ i) scanf("%d", &a[i]);
    sort(a, a + n);
    ll res = 0;
    for (int i = 0; i < n; ++ i)
    {
        res += abs(a[i] - a[n / 2]);
    }
    cout << res << endl;
    return 0;
}