当前位置:   article > 正文

状态压缩动态规划例题_蒜头君喜欢中心对称的字符串,即回文字符串。现在蒜头君手里有一个字符串 ss,蒜头

蒜头君喜欢中心对称的字符串,即回文字符串。现在蒜头君手里有一个字符串 ss,蒜头

前言

当元素数量较小(不超过20)时,想要存储每个元素取或不取,可以借助位运算压缩状态。空间复杂度为 O ( 2 n ) O(2^n) O(2n)

消除字符串

蒜头君喜欢中心对称的字符串,即回文字符串。现在蒜头君手里有一个字符串 SS,蒜头君每次都会进行这样的操作:从 SS 中挑选一个回文的子序列,将其从字符串 SS 中去除,剩下的字符重组成新的字符串 SS。

蒜头君想知道,最少可以进行多少次操作,可以消除整个字符串。

输入格式
输入一行。输入一个字符串 SS(1≤length(S)≤16),字符串均由小写字母组成。

输出格式
输出一行,输出一个整数,表示消除整个字符串需要的最少操作次数。

样例输入
abaccba
样例输出
2
思路:
状压dp。每次都是删去集合的子集,因此通过枚举子集来进行dp。用 d p [ i ] dp[i] dp[i]表示子集i所需要的操作步骤数。

代码:

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int inf=0x3f3f3f3f;
string st;
//判断是否回文串
int judge(int x){
	string st1="",st2;
	int cot=0;
	while(x){
		if(x&1)st1+=st[cot];
		x>>=1;
		cot++;
	}
	st2=st1;
	reverse(st1.begin(),st1.end());
	if(st1==st2)return 1;
	return 0;
}

int dp[70000];
int main(){
	cin>>st;
	int len=st.size();
	//枚举子集
	for(int i=1;i<(1<<len);i++){
		//初始化
		judge(i)?dp[i]=1:dp[i]=inf;
		//枚举i的所有子集
		for(int j=i;j;j=(j-1)&i)
		//子集和子集的补集
		  dp[i]=min(dp[i],dp[j]+dp[j^i]); 
    }
    cout<<dp[(1<<len)-1]<<endl;
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

蒜头君的积木

问题描述

蒜头君酷爱搭积木,他用积木搭了 n 辆重量为 wi的小车和一艘最大载重量为 W 的小船,他想用这艘小船将 n 辆小车运输过河。每次小船运载的小车重量不能超过 W。另外,小船在运载小车时,每辆小车会对小船有一个损坏值si,当多辆小车一起运载时,该趟运载对小船的损坏值为船上所有小车的最大损坏值。
现在蒜头君想知道,如何用小船运载 n 辆小车,可以使得对小船造成的总损坏值最小。

输入格式

第一行输入两个数 W 和 n(100≤w≤400,1≤n≤16),分别表示小船的最大载重量和小车总数。
接下来输入 n 行,每行输入两个整数si和 wi(1≤si ≤50,10≤wi≤100),分别表示每辆小车对小船的损坏值和每辆小车的重量。
输出格式
输出一行,输出一个整数,表示用小船运载 nn 辆小车,最小的总损坏值。

样例输入

90 4
32 50
15 20
40 50
13 40

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int W, n;
int w[16], s[16];
//预先处理每一种子集情况的花费
int maxs(int n) {
    int ans = 0;
    int cnt = 0;
    int weight = 0;
    while (n) {
        cnt++;
        if (n & 1) {
            ans = max(ans, s[cnt - 1]);
            weight += w[cnt - 1];
        }
        n >>= 1;
        if (weight > W) {
            ans = 11111111;
            break;
        }
    }
    return ans;
}

int main() {
    cin >> W >> n;
    for (int t = 0; t < n; t++) {
        cin >> s[t] >> w[t];
    }
    int cnt = (1 << n) - 1;
    int dp[cnt + 1];
    memset(dp, 0, sizeof(dp));
    //每个子集损坏值
    for (int i = 1; i <= cnt; i++)
        dp[i] = maxs(i);
    int res = 10000;
    for (int i = 1; i <= cnt; i++) {
        int ans = 0;
        //该子集的补集的列举
        for (int j = ~i & (cnt); j; j = (j - 1) & (~i & cnt)) {
            ans = min(dp[~i & cnt], dp[j] + dp[(~i & cnt) ^ j]);
        }
        ans += dp[i];
        res = min(res, ans);
    }
    cout << res;
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50

法二:

#include <iostream>
#include <cstring>
#include <algorithm>
int MAXN=0x3f3f3f3f;
using namespace std;
 
 
int main()
{
    int W, n, s[20],w[20];
    cin >> W >> n;
    for(int i = 1; i <= n; i++)
        cin >> s[i] >> w[i];
 
    int pp = 0;
    int dp[(1 << 16) + 1];
 
    //初始化,伤害值最大
    memset(dp, MAXN, sizeof(dp));
 
    //全部先预处理好每个状态
    for(int t = 0; t < (1 << n); t++)
    {
        int ss = 0, ww = 0;
        int id = 1;
 
        for(int tmp = t; tmp; tmp = tmp >> 1)//找出t这个状态下的最大伤害值
        {
            if(tmp & 1)
            {
                ss = max(ss, s[id]);
                ww += w[id];
            }
            id++;
        }
 
        if(ww > W)//t这个状态下,超过船的载重量了
            continue;
 
        dp[t] = ss;
    }
 
    for(int t = 0; t < (1 << n); t++)
    {
        for(int i = t; i; i=(i-1)&t)//枚举t的每个子集
 
        {
            dp[t] = min(dp[t], dp[i] + dp[i^t]);//更新dp[t]的值
        }
    }
 
    cout << dp[(1 << n) - 1] << endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/码创造者/article/detail/799598
推荐阅读
相关标签
  

闽ICP备14008679号