头像

Adam


访客:2008

离线:20天前


活动打卡代码 AcWing 135. 最大子序和

Adam
2个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5+10;
int w[N], s[N], min_v[N];
deque<int> q; // fornt in, tail out
// f[i] is the maximum sum for sequeces that has a size smaller than m and ending at w[i].
// f[i] = max(s[i] - s[i-1], s[i] - s[i-2], ..., s[i] - s[i-m])
// f[i] could 
int main (){
    int n, m;
    cin >> n >> m;
    // cout << "0 ";
    for (int i=1; i<=n; i++) {
        cin >> w[i];
        s[i] = s[i-1] + w[i];
        // cout << s[i] << " ";
    }
    // cout << endl;
    for (int i=0; i<=n; i++) {
        while(!q.empty() && s[i] < s[q.front()]) q.pop_front();
        q.push_front(i);
        if (!q.empty() && (q.front() - q.back() + 1) > m) q.pop_back();
        min_v[i] = s[q.back()];
        // cout << min_v[i] << " ";
    }
    // cout << endl;
    int res = INT_MIN;
    for (int i=1; i<=n; i++) {
        res = max(res, s[i] - min_v[i-1]);
    }
    cout << res;
}


活动打卡代码 AcWing 479. 加分二叉树

Adam
2个月前
#include <bits/stdc++.h>

using namespace std;
const int N = 50;
int f[N][N], g[N][N], w[N];
int n;
void preorder(int l, int r) {
    int root = g[l][r];
    cout << g[l][r] << " ";
    if (root > l) {
        preorder(l, root-1);
    }
    if (root < r) {
        preorder(root+1, r);
    }
}


void init() {
    memset(f, -0x3f, sizeof f);
    for (int i=1; i<=n; i++) {
        f[i][i] = w[i];
        g[i][i] = i;
    }
}
int main() {
    cin >> n;
    for(int i=1; i<=n; i++) cin >> w[i];
    init();
    for(int len=2; len <= n; len++) {
        for (int left=1; left + len - 1 <= n; left ++) {
            int right = left + len - 1;
            int res = INT_MIN;
            int res_k = -1;
            for (int k=left; k<=right; k++) {
                int left_v = (left > k-1) ? 1: f[left][k-1];
                int right_v = (k+1 > right) ? 1 : f[k+1][right];
                int tmp = left_v * right_v + w[k];
                if (tmp > res) {
                    res = tmp;
                    res_k = k;
                }
            }
            f[left][right] = res;
            g[left][right] = res_k;
        }
    }
    cout << f[1][n] << endl;
    preorder(1, n);
}


活动打卡代码 AcWing 1068. 环形石子合并

Adam
2个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 505;
int w[N], s[N];
int f[N][N], g[N][N]; // f[i, j]
int main(){
    int n;
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> w[i];
        w[i+n] = w[i];
    }
    memset(f, -0x3f, sizeof f);
    memset(g, 0x3f, sizeof g);
    for (int i=1; i<=2*n; i++) {
        f[i][i] = 0;
        g[i][i] = 0;
        s[i] = s[i-1] + w[i];
    }
    for (int len=2; len <= n; len++){
        for (int i=1; (i+len-1)<=2*n; i++) {
            int j=i+len-1;
            int res = INT_MAX;
            int res2 = INT_MIN;
            for (int k=i; k<j; k++) {
                res = min(res, f[i][k] + f[k+1][j] + (s[j] - s[i-1]));
                res2 = max(res2, g[i][k] + g[k+1][j] + (s[j] - s[i-1]));
            }
            f[i][j] = res;
            g[i][j] = res2;
        }
    }
    int ans = INT_MAX;
    int ans2 = INT_MIN;
    for (int i=1; i<=n; i++) {
        ans = min(ans, f[i][i+n-1]);
        ans2 = max(ans2, g[i][i+n-1]);
    }
    cout << ans << endl;
    cout << ans2 << endl;
}


活动打卡代码 AcWing 1058. 股票买卖 V

Adam
2个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10;
int f[N][3];
int w[N];
int main () {
    int n;
    cin >> n;
    for (int i=1; i<=n; ++i) cin >> w[i];
    memset(f, -0x3f, sizeof f);
    f[1][0] = 0;
    f[1][1] = -w[1];
    for (int i=2; i<=n; i++) {
        f[i][0] = f[i-1][0];
        f[i][1] = f[i-1][1];
        f[i][0] = max(f[i][0], f[i-1][2]);
        f[i][1] = max(f[i-1][0] - w[i], f[i][1]);
        f[i][2] = f[i-1][1] + w[i];
    }
    cout << max(f[n][0], f[n][2]);
}


活动打卡代码 AcWing 1057. 股票买卖 IV

Adam
2个月前
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int K = 110;
int f[N][2][K];
int w[N];
// f i j 走了i步,进行了j次买卖,目前是0/1仓位的最大收益
int main() {
    int n, k;
    cin >> n >> k;
    for (int i=1; i<=n; i++) cin >> w[i];
    memset(f, -0x3f, sizeof f);
    for (int i=1; i<=n; i++) {
        f[i][0][0] = 0;
    }
    f[1][0][0] = 0;
    f[1][1][1] = -w[1];
    for (int i=2; i<=n; i++) {
        for (int j=1; j <= k; j++) {
            f[i][1][j] = max(f[i-1][1][j], f[i-1][0][j-1] - w[i]);
            f[i][0][j] = max(f[i-1][0][j], f[i-1][1][j] + w[i]);
        }
    }
    int res = 0;
    for (int i=0; i<=k; i++) {
        res = max(res, f[n][0][i]);
    }
    cout << res << endl;
}


活动打卡代码 AcWing 1049. 大盗阿福

Adam
2个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
int f[2], w[N];

int main () {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        memset(f, 0, sizeof f);
        memset(w, 0, sizeof w);
        for (int i=1; i<=n; i++) {
            cin >> w[i];
        }
        for (int i=1; i<=n; i++) {
            int tmp = f[0];
            f[0] = max(f[0], f[1]);
            f[1] = tmp + w[i];
        }
        cout << max(f[0], f[1]) << endl;
    }
}


活动打卡代码 AcWing 323. 战略游戏

Adam
2个月前
#include <bits/stdc++.h>
using namespace std;
const int N = 2000;
int f[N][2];
bool st[N];
vector<vector<int>> edges;
void add(int a, int b) {

    edges[a].push_back(b);
}
void dfs(int u) {
    if (edges[u].empty()) {
        f[u][0] = 0;
        f[u][1] = 1;
        return;
    }
    f[u][1] = 1;
    for (auto i: edges[u]) {
        dfs(i);
        f[u][1] += min(f[i][1], f[i][0]);
        f[u][0] += f[i][1];
    }
}
int main() {
    int n;
    while(cin >> n) {
        memset(f, 0, sizeof f);
        memset(st, 0, sizeof st);
        edges.clear();
        edges = vector<vector<int>>(n, vector<int>());
        int a, b;
        for (int i=0; i<n;i++) {
            scanf("%d:(%d)", &a, &b);
            for (int i=0; i<b; i++) {
                int c;
                cin >> c;
                add(a, c);
                st[c] = true;
            }
        }
        int root=0;
        while(root < n && st[root]) root ++;
        dfs(root);
        cout << min(f[root][0], f[root][1]) << endl;
    }
}



Adam
3个月前
#include<bits/stdc++.h>
using namespace std;
int dp[1010];
int w[1010];
int main() {
    int n;
    cin >> n;
    int res=0;
    for (int i=0; i<n; i++) cin >> w[i];
    for (int i=0; i<n; i++) {
        int __max=0;
        dp[i] = w[i];
        for (int j=0;j<i; j++) {
            if (w[i] > w[j]) {
                __max = max(__max, dp[j]);
            }
        }
        dp[i] += __max;
        res = max(dp[i], res);
    }
    cout << res;
}


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

Adam
3个月前
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
vector<PII> f;
const int N = 6e3;
int dp[N];

int main() {
    int n;
    cin >> n;
    for (int i=0; i<n;i ++) {
        int a, b;
        cin >> a >> b;
        f.push_back({a, b});
    }
    sort(f.begin(), f.end());
    int res = 0;
    for (int i=0; i<n; i++) {
        dp[i] = 1;
        for (int j=0; j<i; j++) {
            if (f[j].second < f[i].second) dp[i] = max(dp[i], dp[j] + 1);
        }
        res = max(res, dp[i]);
    }

    cout << res;
}


活动打卡代码 AcWing 482. 合唱队形

Adam
3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 2e3;
int w[N], f[N], f2[N];
int main() {
    memset(w, 0, sizeof w);
    int n;
    int res=0;
    cin >> n;
    for (int i=1; i <= n; i++) {
        cin >> w[i];
    }

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

    for (int i=n; i>0; --i) {
        f2[i] = 1;
        for (int j=n; j>i; --j) {
            if (w[j] < w[i]) f2[i] = max(f2[i], f2[j] + 1);
        }
    }

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