头像

goontry

dongporen.github.io


访客:8638

离线:8个月前


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

goontry
10个月前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

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

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

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

    cout << f[m] << endl;

    return 0;
}


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

goontry
10个月前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 25000;

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

int main()
{
    cin >> n >> m;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        int a, b, s;
        cin >> a >> b >> s;

        int k = 1;
        while(k <= s) 
        {
            cnt++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0)
        {
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

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

    cout << f[m] << endl;

    return 0;
}


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

goontry
10个月前

暴力法 O(nmk)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

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

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 = 1; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            for (int k = 1; k <= s[i]; k++)
            {
                if (v[i] * k <= j)  f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
            }
        }

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

    return 0;
}


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

goontry
10个月前

暴力法 o(nmk)

#include <iostream>
#include <algorithm>

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 = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            for (int k = 1; j >= v[i] * k; k++)
            {
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
            }
        }

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

    return 0;
}

等式变化 O(nm)

#include <iostream>
#include <algorithm>

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

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

    return 0;
}

降维优化 O(nm)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

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++)
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }

    cout << f[m] << endl;

    return 0;
}


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

goontry
10个月前

暴力法 O(nm)

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;
int n, V;
int v[N], w[N];
int f[N][N];

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

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

    cout << f[n][V] << endl;

    return 0;
}

优化版本

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;
int n, V;
int v[N], w[N];
int f[N];

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

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

    cout << f[V] << endl;

    return 0;
}


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

goontry
10个月前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310, INF = 1e9;;
int n;
int s[N];
int f[N][N];

int main() {

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &s[i]);

    for (int i = 1; i <= n; i++) s[i] += s[i - 1];

    for (int len = 1; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++)
        {
            int l = i, r = l + len; 
            f[l][r] = INF;
            for (int k = i; k < r; k++)
            {
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l-1]);
            }
        }

    printf("%d\n", f[1][n]);
    return 0;
}



goontry
10个月前
#include <iostream>
#include <algorithm>

using namespace std;

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

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s%s", a + 1, b + 1);

    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]);
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }

    printf("%d\n", f[n][m]);

    return 0;
}



goontry
10个月前
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;

int n;
int a[N];
int f[N];

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

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

    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, f[i]);
    cout << res << endl;

    return 0;
}


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

goontry
10个月前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;
int n;
int a[N][N];
int f[N][N];

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

    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= i + 1; j++)
            f[i][j] = -INF;

    f[1][1] = a[1][1];
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= i; j++)
            f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j];

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

    return 0;
}


活动打卡代码 AcWing 872. 最大公约数

goontry
11个月前
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    scanf("%d", &n);
    while (n--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int res = gcd(a, b);
        printf("%d\n", res);
    }
    return 0;
}