头像

Obito_




在线 



Obito_
1小时前
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1010;
int d[N], dp[N];
int n;

int main() {
    cin >> n;
    for(int i = 0; i < n; ++i) cin >> d[i];
    for(int i = 0; i < n; ++i) {
        dp[i] = 1;
        for(int j = 0; j < i; ++j) {
            if(d[i] > d[j]) dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    int res = 0;
    for(int i = 0; i < n; ++i) res = max(res, dp[i]);
    cout << res;
    return 0;
}


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

Obito_
1小时前
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 510;
int n;
int dp[N][N];

int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) { 
        for(int j = 1; j <= i; ++j) cin >> dp[i][j];
    }
    for(int i = n; i >= 1; --i) {
        for(int j = 1; j <= i; ++j) {
            dp[i][j] = dp[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1]);
        }
    }
    cout << dp[1][1];
    return 0;
}


活动打卡代码 AcWing 9. 分组背包问题

Obito_
1小时前
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 110;
int v[N][N], w[N][N], s[N];
int dp[N];
int n, m;

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) {
        cin >> s[i];
        for(int j = 0; j < s[i]; ++j) cin >> v[i][j] >> w[i][j];
    }

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

    cout << dp[m];
    return 0;
}


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

Obito_
2小时前
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 12000, M = 2010; // 2000 ~ 2 ^ 12 = 2048 故N开1000*12=12000即可
int w[N], v[N], dp[M];

int main() {
    int n, m;
    cin >> n >> m;
    int cnt = 0;
    for(int i = 1; i <= n; ++i) {
        int k = 1;
        int vi, wi, si;
        cin >> vi >> wi >> si;
        while(si > k) {
            cnt++;
            v[cnt] = vi * k;
            w[cnt] = wi * k;
            si -= k;
            k <<= 1;
        }
        if(si != 0) {
            cnt++;
            v[cnt] = vi * si;
            w[cnt] = wi * si;
        }
    }


    for(int i = 1; i <= cnt; ++i) {
        for(int j = m; j >= v[i]; --j) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        } 
    }
    cout << dp[m];
    return 0;
}


活动打卡代码 AcWing 89. a^b

Obito_
3小时前
#include<iostream>
using namespace std;
typedef long long LL;
int qmi(int a, int b, int p) {
    if(b == 0) return 1 % p;
    if(b & 1) return (LL) a * qmi(a, b - 1, p) % p;
    else {
        int t = qmi(a, b >> 1, p);
        return (LL) t * t % p;
    }
}

int main() {
    int a, b, p;
    cin >> a >> b >> p;
    cout << qmi(a, b, p);
    return 0;
}


活动打卡代码 AcWing 1341. 十三号星期五

Obito_
4小时前
#include<iostream>
using namespace std;

const int days[2][12] = {
                     {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
                     {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}};

int isLeapYear(int year) {
    return (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) ? 1 : 0;
}

int res[7]; // 除了周日比较特殊是res[0],其余例如周一就是res[1], 周二就是res[2]......

int main() {
    int n;
    cin >> n;
    int y = 1900, m = 1, d = 1, cnt = 1; // cnt累计从1900-01-01开始的天数
    while(y < 1900 + n) {
        if(d == 13) res[cnt % 7]++;
        d++, cnt++;
        if(d > days[isLeapYear(y)][m - 1]) d = 1, m++; // 由于这里的月份从1开始,所以得减去1
        if(m > 12) m = 1, y++; 
    }
    cout << res[6] << ' ' << res[0] << ' ' << res[1] << ' ' << res[2] << ' ' << res[3] << ' ' << res[4] << ' ' << res[5];
    return 0;
}



Obito_
4小时前
(暴力枚举) $O(365n)$

核心思想就是不断累计距1900-01-01的天数

#include<iostream>
using namespace std;

const int days[2][12] = {
                     {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
                     {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}};

int isLeapYear(int year) {
    return (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) ? 1 : 0;
}

int res[7]; // 除了周日比较特殊是res[0],其余例如周一就是res[1], 周二就是res[2]......

int main() {
    int n;
    cin >> n;
    int y = 1900, m = 1, d = 1, cnt = 1; // cnt累计从1900-01-01开始的天数
    while(y < 1900 + n) {
        if(d == 13) res[cnt % 7]++;
        d++, cnt++;
        if(d > days[isLeapYear(y)][m - 1]) d = 1, m++; // 由于这里的月份从1开始,所以得减去1
        if(m > 12) m = 1, y++; 
    }
    cout << res[6] << ' ' << res[0] << ' ' << res[1] << ' ' << res[2] << ' ' << res[3] << ' ' << res[4] << ' ' << res[5];
    return 0;
}


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

Obito_
23小时前
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int dp[N][N], v[N], w[N], s[N];
int n, m;
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> v[i] >> w[i] >> s[i];
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j <= m; ++j) {
            for(int k = 0; k <= s[i] && k * v[i] <= j; ++k) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    }
    cout << dp[n][m];
    return 0;
}


活动打卡代码 AcWing 3. 完全背包问题

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


活动打卡代码 AcWing 2. 01背包问题

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