牛客周赛71（字符串，状压dp）
目录
B. 宝石手串
（1）两种扩容方式：
// 法一：直接加（通常用于拼接字符串）
s += s
// 法二：一个一个字符加（用于加单个字符）
for (int i = len; i < 2 * len; i ++)
s.push_back(s[i - len]);
// 错误方法，s是一个容器，有大小，此方法会越界
for (int i = len; i < 2 * len; i ++)
s[i] = s[i - len];（2）每个字符记录上次出现位置，下次出现更新该字符最短间距
（3）dis数组值为 len - 1 时说明该字符只出现了一次，第二个是复制而来，该情况也要排除
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
int t, n, ans, h[30], vis[30], dis[30];
string s;
int main()
{
cin >> t;
while (t --)
{
cin >> n >> s;
ans = INF;
int len = s.length();
s += s;
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
for (int i = 0; i < 2 * len; i ++)
{
int x = s[i] - 'a';
if (!vis[x])
{
h[x] = i;
vis[x] = 1;
}
else
{
dis[x] = min(dis[x], i - h[x] - 1);
h[x] = i;
}
}
for (int i = 0; i < 30; i ++)
if(dis[i] != len - 1)
ans = min(ans, dis[i]);
if (ans == INF)
cout << "-1" << '\n';
else
cout << ans << '\n';
}
return 0;
}
D. 气球谜题
（1）memset无法赋 1e18，只能 for 循环赋值
（2）dp[ i ][ j ] [ k ]：第 i 个气球颜色为 j ，出现过的颜色集合为 k
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, INF = 1e18;
int n, ans, a[N], dp[N][5][10];
string s;
signed main()
{
cin >> n >> s;
s = '0' + s;
for(int i = 1; i <= n; i ++){
for(int j = 0; j <= 2; j ++){
for(int k = 1; k < 8; k ++){
dp[i][j][k] = INF;
}
}
}
for (int i = 1; i <= n; i ++)
cin >> a[i];
for (int j = 0; j <= 2; j ++)
{
if (s[1] - '0' == j)
dp[1][j][1 << j] = 0;
else
dp[1][j][1 << j] = a[1];
}
for (int i = 2; i <= n; i ++)// 当前在第 i 个气球
for (int j = 0; j <= 2; j ++)// 当前第 i 个气球的颜色
for (int k = 1; k < 8; k ++)
{
//当前集合里面有 j --> j 已经出现过
if (k >> j & 1)
{
if (s[i] - '0' == j)
dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k]);
else
dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k] + a[i]);
}
//当前集合里面没有 j --> j 还未出现过, 现在要变成 j
// --> 第 i - 1 个气球一定不是 j
else
{
// 枚举第 i - 1 个气球的颜色
for (int l = 0; l <= 2; l ++)
{
// k >> l & 1为真：前 i - 1 个气球的颜色集合里必须有 l，因为 i - 1 的颜色为 l
// j != l 为真：当前第 i 个气球颜色肯定不能和第 i - 1 个气球颜色相等，若相等则违背集合没有颜色 j 的大条件
// s[ i ] - '0' == j 和 != j ：分类当前第 i 个气球颜色是否为 j ，需不需要染成 j
// 因为 k 和 j 都还在大循环里枚举，并不能保证第一个和第二个条件自然成立，因此需要加入 if 中判断
if (k >> l & 1 && l != j && s[i] - '0' == j)
dp[i][j][k | 1 << j] = min(dp[i][j][k | 1 << j], dp[i - 1][l][k]);
if (k >> l & 1 && l != j && s[i] - '0' != j)
dp[i][j][k | 1 << j] = min(dp[i][j][k | 1 << j], dp[i - 1][l][k] + a[i]);
}
}
}
ans = INF;
for (int j = 0; j <= 2; j ++)
for (int k = 1; k < 8; k ++)
ans = min(ans, dp[n][j][k]);
cout << ans;
return 0;
}原文地址：https://blog.csdn.net/2301_81608637/article/details/144425401
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！