【今日三题】添加字符(暴力枚举) / 数组变换(位运算) / 装箱问题(01背包)

添加字符(暴力枚举)

  • 添加字符

当在A的开头或结尾添加字符直到和B长度相等时，要求对应位置不相等的最少字符。因为我们总有方法保证在A的长度和B相等时，新添加的字符和B对应位置相同，所以对应位置字符不同可以只在A原始串中出现。所以只需要枚举A相对于B不同位置时的最小结果。

代码语言：javascript代码运行次数：0运行复制
#include <iostream>
#include <string>
using namespace std;

int main()
{
    string a, b;
    cin >> a >> b;
    int m = a.size(), n = b.size();
    int res = 51;
    for (int i = 0; i <= n - m; i++)
    {
        int cnt = 0;
        for (int j = 0; j < m; j++)
        {
            if (a[j] != b[i + j]) cnt++;
        }
        res = min(res, cnt);
    }
    cout << res << endl;
    return 0;
}

数组变换(位运算)

  • 数组变换

满足题意的条件是：对于最大值而言，能整除其他所有值，并且除数是2的倍数。

判断一个数是否是2的倍数，最常见的方法是：x - (x & -x) == 0 和 x & x - 1 == 0。

代码语言：javascript代码运行次数：0运行复制
#include <iostream>
using namespace std;

int arr[51];
int n, m;

bool func()
{
    for (int i = 0; i < n; i++) 
    {
        if (m % arr[i]) return false;
        int x = m / arr[i];
        if (x & (x - 1)) return false;
    }
    return true;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        m = max(m, arr[i]);
    }
    if (func()) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0; 
}

装箱问题(01背包)

  • 装箱问题

定义状态 dp[i][j] 表示从前 i 个物品中挑选，总体积不超过j，此时物品总体积的最大值。

代码语言：javascript代码运行次数：0运行复制
#include <iostream>
using namespace std;

int v, n;
int dp[31][20001];
int a[31];

int main()
{
    cin >> v >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= v; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= a[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]] + a[i]);
        }
    }
    cout << v - dp[n][v] << endl;
    return 0;
}
代码语言：javascript代码运行次数：0运行复制
#include <iostream>
using namespace std;

int v, n;
int dp[20001];
int a[31];

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

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

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