头像

巴扎嘿




离线:10天前



巴扎嘿
12天前
#include<iostream>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N], t1[N][N], t2[N][N];
int main()
{
    cin >> n >> m;
    cin >> 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);
        }
    }
    cout << f[n][m];
    return 0;
}



巴扎嘿
12天前
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 101000;
int n;
int a[N];
int f[N];
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ )
    cin >> a[i];
    f[0] = a[1];
    int maxi = 1;
    for(int i = 1; i <= n; i ++ )
    {
        int *t = lower_bound(f, f + maxi, a[i]);
        if(t - f == maxi) maxi ++ ;
        *t = a[i];
    }
    cout << maxi;
    return 0;
}



巴扎嘿
12天前
#include<iostream>
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];
    a[0] = -2e9;
    int maxi = 0;
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 0; j < i; j ++)
        {
            if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
        }
        maxi = max(f[i], maxi);
    }
    cout << maxi;
    return 0;
}


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

巴扎嘿
12天前

注意三角形外的初值

#include<iostream>
#include<cstring>
using namespace std;
const int N = 505;
int f[N][N];
int main()
{
    int n;
    cin >> n;
    int maxi = 0;
    cin >> f[1][1];
    for(int i = 2; i <= n; i ++ )
    {
        for(int j = 1; j <= i; j ++ )
        {
            int t;
            cin >> t;
            f[i][j] = -2e9;
            if(j <= i - 1)f[i][j] = f[i - 1][j] + t;
            if(j - 1)f[i][j] = max(f[i][j], f[i - 1][j - 1] + t);
        }
    }
    for(int i = 1; i <= n; i ++ )
    {
        maxi = max(maxi, f[n][i]);
    }
    cout << maxi;
    return 0;
}
#include<iostream>
#include<cstring>
using namespace std;
const int N = 505;
int a[N][N];
int f[N][N];
int main()
{
    int n;
    cin >> n;
    int maxi = 0;
    for(int i = 1; i <= n; i ++ )
    for(int j = 1; j <= i; j ++ )
    cin >> a[i][j], f[i][j] = -2e9;
    for(int i = 1; i < n; i ++ )
    {
        f[i][i + 1] = f[i][0] = -2e9;
        f[i][i + 1] = -2e9;
    }
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= i; j ++ )
        {
            f[i][j] = f[i - 1][j] + a[i][j];
            f[i][j] = max(f[i][j], f[i - 1][j - 1] + a[i][j]);
        }
    }
    for(int i = 1; i <= n; i ++ )
    {
        maxi = max(maxi, f[n][i]);
    }
    cout << maxi;
    return 0;
}


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

巴扎嘿
12天前
#include<iostream>
using namespace std;
const int N = 110;
int n, m;
int s[N], v[N][N], w[N][N];
int f[N][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 = 0; j <= m; j ++ )
        {
            f[i][j] = f[i - 1][j];
            for(int k = 1; k <= s[i]; k ++ )
            {
                if(j >= v[i][k])f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
            }
        }
    }
    cout << f[n][m];
    return 0;
}


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

巴扎嘿
12天前
#include<iostream>
using namespace std;
const int N = 20000, M = 2010;
int n, m;
int f[M], v[N], w[N], idx;
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s)
        {
            idx ++ ;
            v[idx] = a * k;
            w[idx] = b * k;
            s -= k;
            k *= 2;
        }
        if(s > 0)
        {
            idx ++ ;
            v[idx] = s * a;
            w[idx] = s * b;
        }
    }
    n = idx;
    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];
    return 0;
}


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

巴扎嘿
12天前
#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int n, m;
int v[N], w[N], s[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 = 0; j <= m; j ++ )
        {
            for(int k = 0; k <= s[i] && k * v[i] <= j; k ++ )
            f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
        }
    }
    cout << f[n][m];
    return 0;
}


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

巴扎嘿
12天前
#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int n, m;
int v[N], w[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 = m; j >= v[i]; j -- )
        {
            for(int k = 0; k * v[i] <= j; k ++ )
            f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
        }
    }
    cout << f[m];
    return 0;
}
#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int n, m;
int v[N], w[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(j >= v[i])f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
    }
    cout << f[n][m];
    return 0;
}
#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int n, m;
int v[N], w[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];
    return 0;
}


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

巴扎嘿
12天前

二维

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n, v[N], w[N], ve;
int f[N][N];
int main()
{
    cin >> n >> ve;
    for(int i = 1; i <= n; i ++ )
    cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 0; j <= ve; 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]);
        }
    }
    cout << f[n][ve];
    return 0;
}

一维

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



巴扎嘿
29天前
#include<iostream>
using namespace std;
const int N = 105;
bool a[N][N];
int n;
int gauss()
{
    int r, c;
    for(r = 0, c = 0; c < n; c ++ )
    {
        int t = -1;
        for(int i = r; i < n; i ++ )
        {
            if(a[i][c])
            {
                t = i;
                break;
            }
        }
        if(t == -1) continue;

        for(int i = 0; i < n + 1; i ++ )swap(a[t][i], a[r][i]);
        for(int i = r + 1; i < n; i ++ )
        if(a[i][c])
        for(int j = 0; j < n + 1; j ++ )
        a[i][j] ^= a[r][j];
        r ++ ;
    }
    if(r != n)
    {
        for(int i = r; i < n; i ++ )
        if(a[i][n])return 3;
        return 2;
    }
    for(int i = n - 1; i >= 0; i -- )
    {
        for(int j = i - 1; j >= 0; j -- )
        {
            if(a[j][i])a[j][n] ^= a[i][n];
        }
    }
    return 1;
}
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++ )
    for(int j = 0; j < n + 1; j ++ )
    scanf("%d", &a[i][j]);

    int t = gauss();
    if(t == 1)
    {
        for(int i = 0; i < n; i ++ )
        {
            printf("%d\n", a[i][n]);
        }
    }
    else if(t == 2)
    {
        printf("Multiple sets of solutions");
    }
    else
    {
        printf("No solution");
    }
    return 0;
}