【今日三题】小红的口罩(小堆)春游(模拟)数位染色(01背包)

admin管理员组

文章数量:1027213

【今日三题】小红的口罩(小堆) / 春游(模拟) / 数位染色(01背包)

小红的口罩(小堆)

• 小红的口罩

代码语言：javascript代码运行次数：0运行复制

#include <iostream>
#include <queue>
using namespace std;

int n, k, sum, res;
priority_queue<int, vector<int>, greater<int>> pq;

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        pq.push(a);
    }
    while (sum <= k)
    {
        res++;
        int t = pq.top();
        sum += t;
        pq.pop();
        pq.push(t * 2);
    }
    cout << res - 1 << endl;
    return 0;
}

---

春游(模拟)

• 春游

首先让尽可能多的人乘坐单人价更低的船，然后把剩余的人分情况讨论。 如果双人船的单人价更低，则最后可能剩一人或刚好坐满，这一个人可以选择做双人船，或三人船、或和前面两个人一起坐三人船； 同理如果三人船的单人价更低，则最后可能剩一人，两人，或刚好坐满，如果是一人则可以选择做双人船，三人船，或和前面三个人一起坐两条双人船；同理如果是两人则也可以和前面三个人一起坐三条双人船。

代码语言：javascript代码运行次数：0运行复制

#include <iostream>
using namespace std;

using ll = long long;
ll t, n, a, b;

int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n >> a >> b;
        ll sum = 0;
        if (n <= 2) sum = min(a, b);
        else if (a * 3 < b * 2)
        {
            sum += n / 2 * a;
            if (n % 2) sum += min(min(a, b), b - a);
        }
        else
        {
            sum += n / 3 * b;
            if (n % 3 == 1) sum += min(min(a, b), 2 * a - b);
            if (n % 3 == 2) sum += min(min(a, b), 3 * a - b);
        }
        cout << sum << endl;
    }
    return 0;
}

---

数位染色(01背包)

• 数位染色

代码语言：javascript代码运行次数：0运行复制

#include <iostream>
#include <string>
using namespace std;

string s;
int sum;

int main() 
{
    cin >> s;
    for (auto ch : s) sum += (ch - '0');
    if (sum % 2 == 0)
    {
        sum /= 2;
        int dp[20][200] = {};
        int n = s.size();
        for (int i = 0; i <= n; i++) dp[i][0] = true;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= sum; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= (s[i - 1] - '0'))  
                    dp[i][j] = dp[i][j] || dp[i - 1][j - (s[i - 1] - '0')];
            }
        }
        if (dp[n][sum]) 
        {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

代码语言：javascript代码运行次数：0运行复制

#include <iostream>
#include <string>
using namespace std;

string s;
int sum;

int main() 
{
    cin >> s;
    for (auto ch : s) sum += (ch - '0');
    if (sum % 2 == 0)
    {
        sum /= 2;
        int dp[200] = {};
        int n = s.size();
        dp[0] = true;
        for (int i = 1; i <= n; i++)
            for (int j = sum; j >= (s[i - 1] - '0'); j--) 
                dp[j] = dp[j] || dp[j - (s[i - 1] - '0')];
        if (dp[sum]) 
        {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-05-05，如有侵权请联系 cloudcommunity@tencent 删除前往查看dpincludeintminsum

【今日三题】小红的口罩(小堆) / 春游(模拟) / 数位染色(01背包)

小红的口罩(小堆)

• 小红的口罩

代码语言：javascript代码运行次数：0运行复制

#include <iostream>
#include <queue>
using namespace std;

int n, k, sum, res;
priority_queue<int, vector<int>, greater<int>> pq;

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        pq.push(a);
    }
    while (sum <= k)
    {
        res++;
        int t = pq.top();
        sum += t;
        pq.pop();
        pq.push(t * 2);
    }
    cout << res - 1 << endl;
    return 0;
}

---

春游(模拟)

• 春游

首先让尽可能多的人乘坐单人价更低的船，然后把剩余的人分情况讨论。 如果双人船的单人价更低，则最后可能剩一人或刚好坐满，这一个人可以选择做双人船，或三人船、或和前面两个人一起坐三人船； 同理如果三人船的单人价更低，则最后可能剩一人，两人，或刚好坐满，如果是一人则可以选择做双人船，三人船，或和前面三个人一起坐两条双人船；同理如果是两人则也可以和前面三个人一起坐三条双人船。

代码语言：javascript代码运行次数：0运行复制

#include <iostream>
using namespace std;

using ll = long long;
ll t, n, a, b;

int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n >> a >> b;
        ll sum = 0;
        if (n <= 2) sum = min(a, b);
        else if (a * 3 < b * 2)
        {
            sum += n / 2 * a;
            if (n % 2) sum += min(min(a, b), b - a);
        }
        else
        {
            sum += n / 3 * b;
            if (n % 3 == 1) sum += min(min(a, b), 2 * a - b);
            if (n % 3 == 2) sum += min(min(a, b), 3 * a - b);
        }
        cout << sum << endl;
    }
    return 0;
}

---

数位染色(01背包)

• 数位染色

代码语言：javascript代码运行次数：0运行复制

#include <iostream>
#include <string>
using namespace std;

string s;
int sum;

int main() 
{
    cin >> s;
    for (auto ch : s) sum += (ch - '0');
    if (sum % 2 == 0)
    {
        sum /= 2;
        int dp[20][200] = {};
        int n = s.size();
        for (int i = 0; i <= n; i++) dp[i][0] = true;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= sum; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= (s[i - 1] - '0'))  
                    dp[i][j] = dp[i][j] || dp[i - 1][j - (s[i - 1] - '0')];
            }
        }
        if (dp[n][sum]) 
        {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

代码语言：javascript代码运行次数：0运行复制

#include <iostream>
#include <string>
using namespace std;

string s;
int sum;

int main() 
{
    cin >> s;
    for (auto ch : s) sum += (ch - '0');
    if (sum % 2 == 0)
    {
        sum /= 2;
        int dp[200] = {};
        int n = s.size();
        dp[0] = true;
        for (int i = 1; i <= n; i++)
            for (int j = sum; j >= (s[i - 1] - '0'); j--) 
                dp[j] = dp[j] || dp[j - (s[i - 1] - '0')];
        if (dp[sum]) 
        {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-05-05，如有侵权请联系 cloudcommunity@tencent 删除前往查看dpincludeintminsum

本文标签： 今日三题小红的口罩(小堆)春游(模拟)数位染色(01背包)