牛客周赛71(字符串,状压dp)

时间:2024-12-15 07:24:29

目录

B. 宝石手串

         D. 气球谜题


 

 

 

 

 

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;
}