头像

Wudiy




离线:1小时前


最近来访(10)
用户头像
尘空
用户头像
VICI_
用户头像
i狗子_5

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

Wudiy
8小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

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

int main(){
    cin >> n;

    f[0][0] = -10000, f[0][1] = -10000, f[0][2] = 0;
    for (int i = 1;i <= n;i ++ ){
        int v;
        cin >> v;
        f[i][0] = max (f[i - 1][0], f[i - 1][2] - v);
        f[i][1] = f[i - 1][0] + v;
        f[i][2] = max (f[i - 1][1], f[i - 1][2]);
    }

    cout << max ( f[n][1], f[n][2]) << endl;
    return 0;
}



Wudiy
8小时前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second
const int N = 32010, M = 70;

int n, m;
int f[M][N];
PII fa[M];
vector<PII> son[M];

int main(){
    cin >> m >> n;

    for (int i = 1; i <= n;i ++ ){
        int v, w, p;
        cin >> v >> w >> p;
        if (p) son[p].push_back({v, v * w});
        else fa[i] = {v, v * w};
    }

    for (int i = 1;i <= n;i ++ ){
        if (fa[i].x) { // 如果第i个是主件
            // 先把主件拿下
            for (int j = fa[i].x;j <= m;j ++ )
                if (j >= fa[i].x) f[i][j] = max (f[i][j], f[i - 1][j - fa[i].x] + fa[i].y);

            // 再遍历每个附件
            for (int j = 0;j < son[i].size();j ++ ){
                for (int k = m;k >= fa[i].x + son[i][j].x;k -- ){
                     // 必须是添加过主件才能添加附件
                    if (f[i][k - son[i][j].x] >= fa[i].y)
                        f[i][k] = max (f[i][k], f[i][k - son[i][j].x] + son[i][j].y);
                }
            }
        }
        // 继承一下
        for (int j = 0;j <= m;j ++ ){
            f[i][j] = max (f[i][j], f[i - 1][j]);
        }
    }
    cout << f[n][m] << endl;

    return 0;
}


活动打卡代码 AcWing 1875. 贝茜的报复

Wudiy
20小时前
#include<bits/stdc++.h>
using namespace std;

int ans;
// 感觉是报复我的
map<char, int> mp1, mp2, a;
string s = "BESIGOM";
void dfs(int u, int x){
    if(u == 7){
        if((a['B'] + a['I']) % 2 && (a['G'] + a['O'] + a['E'] + a['S']) % 2 && a['M'] % 2) return;
        ans += x;
        return;
    }
    char ch = s[u];
    a[ch] = 1, dfs(u + 1, x * mp1[ch]);
    a[ch] = 2, dfs(u + 1, x * mp2[ch]);
}
int main(){
    int n; cin >> n;
    for(int i = 0; i < n; i++){
        char c; int x; cin >> c >> x;
        if(x % 2) mp1[c]++;//字母C中奇数的个数
        else mp2[c]++;//字母C中偶数的个数
    }


    dfs(0, 1);
    cout << ans;
    return 0;
}


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

Wudiy
21小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;

int n, m;
int f[N][110][2];

int main(){
    cin >> n >> m;

    memset(f, -0x3f, sizeof f);

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

    for(int i = 1;i <= n;i ++ ){
        int t;
        cin >> t;
        for (int j = 1;j <= m;j ++ ){
            //有货
            f[i][j][1] = max (f[i - 1][j - 1][0]- t, f[i - 1][j][1]);
            // 无货
            f[i][j][0]= max (f[i - 1][j][0], f[i - 1][j][1] + t);
        }
    }

    int ans = 0;
    for (int i = 0;i <= m;i ++ ) ans = max (ans, f[n][i][0]);

    cout << ans << endl;

    return 0;
}


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

Wudiy
22小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int T, n;
int dp[N][2], a[N];

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

        // dp[0][0] = 0, dp[0][1] = 
        for (int i = 1;i <= n;i ++ ){
            int t;
            cin >> t;
            // if (i - 2 >= 0) dp[i] = max (dp[i - 2] + a[i], dp[i - 1]);
            // else dp[i] = a[i];
            dp[i][0] = max (dp[i - 1][0], dp[i  -1][1]);
            dp[i][1] = dp[i - 1][0] + t;
        }
        cout << max (dp[n][0], dp[n][1]) << endl;
        // cout << dp[n] << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1884. COW

Wudiy
1天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
typedef long long ll;

int n;
char s[N];
ll c[N], o[N], w[N];

int main(){
    cin >> n;

    for (int i = 1;i <= n;i ++ ){
        cin >> s[i];
        if (s[i] == 'C') c[i] = c[i - 1] + 1, o[i] = o[i - 1], w[i] = w[i - 1];
        else if (s[i] == 'O') c[i] = c[i - 1], o[i] = o[i - 1] + 1, w[i] = w[i - 1];
        else c[i] = c[i - 1], o[i] = o[i - 1], w[i] = w[i - 1] + 1;
    }
    ll ans = 0;
    for (int i = 1;i <= n;i ++ ){
        if (s[i] == 'O') ans += (c[i]) * (w[n] - w[i]);
    }
    // cout << ans << endl;
    printf ("%lld\n", ans);

    return 0;
}



Wudiy
1天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010;

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

int main(){
    cin >> n >> m;

    for (int i = 1;i <= n;i ++ ) cin >> v[i] >> w[i];

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

    // f[1][m] 是最大值

    int j = m;
    for (int i = 1;i <= n;i ++ ){
        if (j >= v[i] && (f[i][j] == f[i + 1][j - v[i]] + w[i])){
            cout << i << ' ';
            j -= v[i];
        }
    }

    return 0;
}



Wudiy
1天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

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

int f[N], cnt[N]; // f记录价值, cnt记录数量
int n, m;

int main(){
    cin >> n >> m;

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

    for (int i = 0;i < n;i ++ ){
        int v, w;
        cin >> v >> w;
        for (int j = m;j >= v;j -- ){
            int val = f[j - v] + w;
            if (val > f[j]){
                f[j] = val;
                cnt[j] = cnt[j - v];
            }
            else if (val == f[j]){
                cnt[j] = (cnt[j] + cnt[j - v]) % mod;
            }
        }
    }

    cout << cnt[m] << endl;

    return 0;
}



Wudiy
1天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 110;

int n, m;
int root;
vector<int> vc[N];
int f[N][N];
int v[N], w[N];

void dfs (int d, int x){
    for (int i = v[d];i <= x;i ++ ) f[d][i] = w[d];

    for (int i = 0;i < vc[d].size();i ++ ){
        int y = vc[d][i];
        dfs (y, x - v[d]); // 先给子节点赋值
        for (int j = x;j >= v[d];j -- ){
            for (int k = 0;k <= j - v[d];k ++ ){
                f[d][j] = max (f[d][j], f[d][j - k] + f[y][k]);
            }
        }
    }
}

int main(){
    cin >> n >> m;

    for (int i = 1;i <= n;i ++ ){
        int p;
        cin >> v[i] >> w[i] >> p;
        if (p == -1) root = i;
        else vc[p].push_back(i);
    }

    dfs (root, m);

    cout << f[root][m] << endl;

    return 0;
}


活动打卡代码 AcWing 1904. 奶牛慢跑

Wudiy
3天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

int n;
stack<int> stk;

int main(){
    cin >> n;
    stk.push(-1);
    for (int i = 0;i < n;i ++ ){
        int x, v;
        cin >> x >> v;

        if (v >= stk.top()) stk.push(v);
        else{
            while (stk.top() > v) stk.pop();

            stk.push(v);
        }
    }

    cout << stk.size() - 1 << endl;

    return 0;
}