头像

dwr




离线:28天前


活动打卡代码 AcWing 426. 开心的金明

dwr
2个月前

2020/12/28 16:12

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 26, M = 30010;

int v[N], w[N], dp[N][M], n, m, p;

int main()
{
    cin >> m >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i];
        w[i] *= v[i];
    }
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            if(v[i] <= j)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
            else
                dp[i][j] = dp[i - 1][j];
    cout << dp[n][m] << endl;
    system("pause");
    return 0;
}



dwr
2个月前

2020/12/28 16:02
一开始的问题出现在组的编号和输入时的次序有出入,因为我将同一组的物品放在了一起,也就是将组的编号数量压缩了,所以出现了问题,代码中样例就会反映问题

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef pair<int, vector<pair<int, int>>> PIV;// 组数和该组的物品数,vecotr中存每个物品的w和v

const int N = 61, M = 32010, P = 6;

int n, m, w[N][P], v[N][P], dp[N][M], s[N];
vector<PIV> f;// 存所有组

/*
4500 12
100 3 0
400 5 0
300 5 0
1400 2 0
500 2 0
800 2 4
1400 5 4
300 5 0
1400 3 8
500 2 0
1800 4 0
440 5 10
*/

int main()
{
    int w0, q0, p0;
    cin >> m >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> w0 >> q0 >> p0;
        if(p0 == 0)// 要新开一组
        {
            PIV tmp;
            tmp.first = i;// 记录组号
            tmp.second.push_back({w0 * q0, w0});// 第一个元素
            f.push_back(tmp);
        }
        else
        {
            int i;
            for(i = 0; i < f.size(); i++)
                if(p0 == f[i].first)// 找到组号
                    break;
            f[i].second.push_back({f[i].second[0].first + w0 * q0, f[i].second[0].second + w0});
        }
    }
    for(auto sets = f.begin(); sets != f.end(); sets++)
    {
        if(sets->second.size() == 3)
        {
            int v = sets->second[2].second + sets->second[1].second - sets->second[0].second;
            int w = sets->second[2].first + sets->second[1].first - sets->second[0].first;
            sets->second.push_back({w, v});
        }
        // cout << sets->first << " -- \n";
        // for(auto unit : sets->second)
        // {
        //     cout << unit.first << " " << unit.second << endl;
        // }
        // cout << endl;
    }

    n = 0;
    for(auto sets = f.begin(); sets != f.end(); sets++)
    {
        n++;
        s[n] = sets->second.size();
        for(int i = 0; i < sets->second.size(); i++)
        {
            w[n][i + 1] = sets->second[i].first;
            v[n][i + 1] = sets->second[i].second;
        }
    }

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

    cout << dp[n][m] << endl;
    system("pause");
    return 0;
}

下面是问题代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 61, M = 32010, P = 6;

int n, m, w[N][P], v[N][P], dp[N][M], s[N];

int main()
{
    int w0, q0, p0, ptr = 0;
    cin >> m >> n;
    // for(int i = 1; i <= n; i++) s[i] = 0;
    for(int i = 1; i <= n; i++)
    {
        cin >> w0 >> q0 >> p0;
        if(p0 == 0)
        {
            ptr++;
            s[ptr]++;
            w[ptr][s[ptr]] = w0 * q0;
            v[ptr][s[ptr]] = w0;
        }
        else
        {
            s[p0]++;
            w[p0][s[p0]] = w[p0][1] + w0 * q0;
            v[p0][s[p0]] = v[p0][1] + w0;
        }
    }
    n = ptr;
    for(int i = 1; i <= n; i++)
    {
        if(s[i] == 3)
        {
            s[i]++;
            w[i][s[i]] = w[i][2] + w[i][3] - w[i][1];
            v[i][s[i]] = v[i][2] + v[i][3] - v[i][1];
        }
        // cout << i << " " << s[i] << " ->\n";
        // for(int j = 1; j <= s[i]; j++)
        // {
        //     cout << w[i][j] << " " << v[i][j] << endl;
        // }
        // cout << endl;
    }
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            for(int k = 0; k <= s[i]; k++)// k = 0表示不选第i组的东西
                if(v[i][k] <= j)
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i][k]] + w[i][k]);
    cout << dp[n][m] << endl;
    system("pause");
    return 0;
}


活动打卡代码 AcWing 1013. 机器分配

dwr
2个月前

2020/12/28 14:53

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 11, M = 16;

int n, m, w[N][M], dp[N][M], way[N];

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

    int j = m;
    for(int i = n; i >= 1; i--)
        for(int k = 0; k <= j; k++)
            if(dp[i][j] == dp[i - 1][j - k] + w[i][k])
            {
                way[i] = k;
                j -= k;
                break;
            }
    for(int i = 1; i <= n; i++) cout << i << " " << way[i] << endl;
    system("pause");
    return 0;
}



dwr
2个月前

2020/12/27 14:09

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

int n, m, v[N], w[N], dp[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++)
            if(v[i] <= j)
                dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - v[i]] + w[i]);
            else
                dp[i][j] = dp[i + 1][j];

    for(int i = 1; i <= n; i++)
        if(m >= v[i] && dp[i][m] == dp[i + 1][m - v[i]] + w[i])
            cout << i << " ", m -= v[i];
    system("pause");
    return 0;
}


活动打卡代码 AcWing 1019. 庆功会

dwr
2个月前

2020/12/27 10:42

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510, M = 6010;

int n, m, s[N], v[N], w[N], dp[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 = m; j >= 0; j--)
            for(int k = 0; k * v[i] <= j && k <= s[i]; k++)
                dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
    cout << dp[m] << endl;
    system("pause");
    return 0;
}


活动打卡代码 AcWing 7. 混合背包问题

dwr
2个月前

2020/12/26 17:41

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 101000;

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

int main()
{
    int a, b, c, cnt = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a >> b >> c;
        if(c == -1)
        {
            cnt++, v[cnt] = a, w[cnt] = b;
        }
        else if(c == 0)
        {
            int num = m / b + 1, k = 1;
            while(k <= num)
            {
                cnt++;
                v[cnt] = k * a;
                w[cnt] = k * b;
                num -= k;
                k <<= 1;
            }
            if(num)
            {
                cnt++;
                v[cnt] = num * a;
                w[cnt] = num * b;
            }
        }
        else
        {
            int k = 1;
            while(k <= c)
            {
                cnt++;
                v[cnt] = a * k;
                w[cnt] = b * k;
                c -= k;
                k <<= 1;
            }
            if(c > 0)
            {
                cnt++;
                v[cnt] = a * c;
                w[cnt] = b * c;
            }
        }
    }
    n = cnt;

    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] << endl;
    system("pause");
    return 0;
}



dwr
2个月前

2020/12/26 16:52

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1010, V = 110, M = 110;

int n, m, v, dp[V][M], vi[N], mi[N], wi[N];

int main()
{
    cin >> n >> v >> m;
    for(int i = 1; i <= n; i++)
        cin >> vi[i] >> mi[i] >> wi[i];
    for(int i = 1; i <= n; i++)
        for(int j = v; j >= vi[i]; j--)
            for(int k = m; k >= mi[i]; k--)
                dp[j][k] = max(dp[j][k], dp[j - vi[i]][k - mi[i]] + wi[i]);
    cout << dp[v][m] << endl;
    system("pause");
    return 0;
}


活动打卡代码 AcWing 1023. 买书

dwr
2个月前

2020/12/26 16:40

/**
 * 子问题包含用10、20、50、100买的问题
 * */

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 11;

int n, dp[N], a[5] = {0, 1, 2, 5, 10};

int main()
{
    cin >> n;
    if(n % 10 == 0)
    {
        n /= 10;
        dp[0] = 1;
        for(int i = 1; i <= 4; i++)
            for(int j = a[i]; j <= n; j++)
                dp[j] += dp[j - a[i]];

        cout << dp[n] << endl;
    }
    else
    {
        puts("0");
    }
    system("pause");
    return 0;
}



dwr
2个月前

2020/12/26 16:13

/**
 * 二维费用背包问题
 * 第一维费用是精灵球数量
 * 第二维费用是体力值
 * 状态的表示是精灵的个数
 * f[i][j][k]表示所有只从前i个物品中选,且花费1不超过j,花费2不超过k的最大值
 * f[i][j][k] = max(f[i - 1][j][k], f[i - 1][j - v1[i]][k - v2[i]] + w[i])
 * 答案在于f[n][精灵球储量][体力值]
 * 体力消耗的最小值就是找m,使得f[n][精灵球储量][m] == f[n][精灵球储量][体力值]
 * */

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010, M = 510, K = 110;

// int V1, V2, n, f[K][N][M], v1[K], v2[K];
int V1, V2, n, f[N][M], v1[K], v2[K];

/*
int main()
{
    cin >> V1 >> V2 >> n;
    for(int i = 1; i <= n; i++) cin >> v1[i] >> v2[i];
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= V1; j++)
        {
            for(int k = 0; k <= V2; k++)
            {
                if(j >= v1[i] && k >= v2[i])
                    f[i][j][k] = max(f[i - 1][j][k], f[i - 1][j - v1[i]][k - v2[i]] + 1);
                else
                    f[i][j][k] = f[i - 1][j][k];
            }
        }
    }
    cout << f[n][V1][V2 - 1] << " ";
    for(int i = 0; i < V2 - 1; i++)
        if(f[n][V1][i] == f[n][V1][V2 - 1])
        {
            cout << V2 - i << endl;
            break;
        }
    system("pause");
    return 0;
}
*/

int main()
{
    cin >> V1 >> V2 >> n;
    for(int i = 1; i <= n; i++) cin >> v1[i] >> v2[i];
    for(int i = 1; i <= n; i++)
    {
        for(int j = V1; j >= v1[i]; j--)
        {
            for(int k = V2; k >= v2[i]; k--)
            {
                f[j][k] = max(f[j][k], f[j - v1[i]][k - v2[i]] + 1);
            }
        }
    }
    cout << f[V1][V2 - 1] << " ";
    for(int i = 0; i <= V2 - 1; i++)
        if(f[V1][i] == f[V1][V2 - 1])
        {
            cout << V2 - i << endl;
            break;
        }
    system("pause");
    return 0;
}


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

dwr
2个月前

2020/12/26 15:01

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 1e5 + 10;

typedef pair<int, int> PII;

int t, n, ans, f[N], dp[N];

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        memset(dp, 0, sizeof(dp));
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) scanf("%d", &f[i]);
        for(int i = 1; i <= n; i++) dp[i] = max(dp[i - 1], dp[i - 2] + f[i]);
        cout << dp[n] << endl;
    }
    system("pause");
    return 0;
}