首页 > 其他分享 >状压DP

状压DP

时间：2023-04-15 12:02:43浏览次数：40  
标签：std int 状压 namespace long using include DP

状压DP

状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。

例题

售货员的难题 洛谷1171

#include<bits/stdc++.h>
using namespace std;
int n,i,j,k,min1,a[25][25],f[1050000][25];
int main()
{
	cin>>n;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			cin>>a[i][j];
	memset(f,64,sizeof(f));
	f[1][1]=0;
	for (i=1;i<1<<n;i+=2)
	{
		for (j=1;j<=n;j++)
		{
			if (!(i>>(j-1)&1))
				continue;
			for (k=1;k<=n;k++)
			{
				if (j==k)
					continue;
				if (!(i>>(k-1)&1)) 
					continue;
				f[i][j]=min(f[i][j],f[i^(1<<(j-1))][k]+a[k][j]);
			}
		}
	}
	min1=2147483647;
	for (i=1;i<=n;i++)
		min1=min(min1,f[(1<<n)-1][i]+a[i][1]);
	cout<<min1<<'\n';
}

单词游戏 洛谷1278

#include<bits/stdc++.h>
using namespace std;
long long n,i,max1,f[1<<16][5];
string s;
struct ff{
	long long bg,ed,len;
}a[20];
long long sc(long long x,long long y)
{
	if (f[x][y]!=-1)
		return f[x][y];
	long long s=0;
	for (int i=0;i<n;i++)
		if ((y==a[i].bg)and(!((1<<i)&x)))
			s=max(s,sc(x|1<<i,a[i].ed)+a[i].len);
	f[x][y]=s;
	return s;
}
int change(char ch)
{
	if (ch=='A')
		return 0;
	if (ch=='E')
		return 1;
	if (ch=='I')
		return 2;
	if (ch=='O')
		return 3;
	if (ch=='U')
		return 4;
}
int main()
{
	cin>>n;
	for (i=0;i<n;i++)
	{
		cin>>s;
		a[i].bg=change(s[0]);
		a[i].ed=change(s[s.length()-1]);
		a[i].len=s.length();
	}
	for (i=0;i<n;i++)
	{
		memset(f,-1,sizeof(f));
		max1=max(max1,sc(1<<i,a[i].ed)+a[i].len);
	}
	cout<<max1<<'\n';
}

平板涂色 洛谷1283

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,i,j,k,s,to,min1,f[1<<17][21];bool ff;
struct sc{
	ll ax,ay,bx,by,c;
}a[40];
vector<ll>b[17];
int main()
{
	cin>>n;
	for (i=0;i<n;i++)
		cin>>a[i].ax>>a[i].ay>>a[i].bx>>a[i].by>>a[i].c;
	for (i=0;i<n;i++)
		for (j=0;j<n;j++)
			if (i!=j)
			{
				if ((a[i].bx==a[j].ax)and((a[i].ay<=a[j].ay)and(a[i].by>=a[j].ay)or(a[i].ay<=a[j].by)and(a[i].by>=a[j].by)or(a[i].ay>=a[j].ay)and(a[i].by<=a[j].by)))
				b[j].push_back(i);
			}
	memset(f,64,sizeof(f));
	for (i=0;i<=20;i++)
		f[0][i]=1;
	for (i=0;i<(1<<n);i++)
	{
		for (j=0;j<n;j++)
		{
			if (!((1<<j)&i))
				continue;
			ff=true;s=1000000;
			for (k=0;k<b[j].size();k++)
			{
				to=b[j][k];
				if ((!((1<<to)&i)))
				{
					ff=false;
					break;
				}
				s=min(s,f[i^(1<<j)][a[to].c]+(!(a[to].c==a[j].c)));
			}
			if (ff)
			{
				for (k=1;k<=20;k++)
					s=min(s,f[i^(1<<j)][k]+(!(a[j].c==k)));
				f[i][a[j].c]=s;
			}
		}
	}
	min1=1000000;
	for (i=1;i<=20;i++)
		min1=min(min1,f[(1<<n)-1][i]);
	cout<<min1<<'\n';
}

互不侵犯 洛谷1896

#include<bits/stdc++.h>
using namespace std;
long long n,m,i,j,k,s,q,p,l,f[15][1050][105];
long long judge(long long x)
{
	int k=0,s=0;
	while (x>0)
	{
		if ((x%2==1)and(k==1))
			return -1;
		k=x%2;
		s=s+k;
		x=x/2;
	}
	if (s<=m)
		return s;
	else
		return -1;
}
bool judge2(long long x,long long y)
{
	int t2=0,w2=0;
	while ((x>0)or(y>0))
	{
		int t=x%2;int w=y%2;
		if ((t==1)and((w==1)or(w2==1)))
			return true;
		if ((w==1)and((t==1)or(t2==1)))
			return true;
		t2=t;w2=w;
		x=x/2;y=y/2;
	}
	return false;
}
int main()
{
	cin>>n>>m;
	for (i=0;i<1<<n;i++)
	{
		q=judge(i);
		if ((q!=-1)and(q<=m))
			f[1][i][q]=1;
	}
	for (i=1;i<=n;i++)
		for (j=0;j<1<<n;j++)
		{
			q=judge(j);
			if (q==-1)	continue;
			for (k=0;k<1<<n;k++)
			{
				p=judge(k);
				if ((p==-1)or(q+p>m)or(judge2(j,k))) continue;
				for (l=q;l<=m-p;l++)
					f[i][k][l+p]=f[i][k][l+p]+f[i-1][j][l];
			}
		}
	for (i=0;i<1<<n;i++)
		s=s+f[n][i][m];
	cout<<s<<'\n';
}

炮兵阵地 洛谷2704

#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,k,l,ma,a[105],b[1050],f[5][1050][1050];
char ch;
int judge(int x)
{
	int s=0,k=0,a=0,b=0;
	while (x>0)
	{
		k=x%2;s+=k;
		if ((k==1)and((a==1)or(b==1)))
			return -1;
		a=b;
		b=k;
		x=x/2;
	}
	return s;
}
int main()
{
	cin>>n>>m;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		{
			cin>>ch;
			if (ch=='H')
				a[i]=a[i]*2+1;
			else a[i]=a[i]*2;
		}
	for (i=0;i<(1<<m);i++)
	{
		b[i]=judge(i);
		if ((!(i&a[1]))and(b[i]!=-1))
			f[1][i][0]=b[i];
	}
	for (i=0;i<(1<<m);i++)
		if ((!(i&a[1]))and(b[i]!=-1))
			for (j=0;j<(1<<m);j++)
				if ((!(j&a[2]))and(b[j]!=-1)and(!(i&j)))
					f[2][j][i]=max(f[2][j][i],f[1][i][0]+b[j]);
	for (i=3;i<=n;i++)
		for (j=0;j<(1<<m);j++)
			if ((b[j]!=-1)and(!(j&a[i])))
				for (k=0;k<(1<<m);k++)
					if ((b[k]!=-1) and (!(k&a[i-1])) and (!(j&k)))
						for (l=0;l<(1<<m);l++)
							if ((b[l]!=-1) and (!(l&a[i-2])) and (!(j&l)) and (!(k&l)))
								f[i%3][j][k]=max(f[i%3][j][k],f[(i-1)%3][k][l]+b[j]);
	for (i=0;i<(1<<m);i++)
		for (j=0;j<(1<<m);j++)
			if ((b[i]!=-1)and(b[j]!=-1)and (!(i&j)))
				ma=max(ma,f[n%3][i][j]);
	cout<<ma<<'\n';
}

Little Pony and Harmony Chest

https://codeforces.com/contest/453/problem/B

#include<bits/stdc++.h>
using namespace std;
int n, m, i, j, k, x, y, t, mi, a[105], b[105], f[105][1 << 18], g[105][1<<18],c[105],d[105];
bool f2;
int main()
{
	cin >> n;
	for (i = 1; i <= n; i++)
		cin >> a[i];
	for (i = 2; i <= 60; i++)
	{
		for (j = 2; j <= i / 2; j++)
			if (i % j == 0)
				break;
		if (j == i / 2 + 1)
			b[++m] = i;
	}
	for (i = 1; i <= 60; i++)
		for (j = 1; j <= m; j++)
			if (i % b[j] == 0)
				d[i] = d[i] ^ (1 << (j - 1));
	memset(f, 0x3f, sizeof(f));
	f[0][0] = 0;
	for (i=1;i<=n;i++)
		for (j = 0; j < 1 << m; j++)
			for (k = 1; k <= a[i]*2; k++)
				if ((d[k] & j) == d[k])
				{
					t = j ^ d[k];
					if (f[i - 1][t] + abs(a[i] - k) < f[i][j])
					{
						f[i][j] = f[i - 1][t] + abs(a[i] - k);
						g[i][j] = k;
					}
				}
	mi = 1e11;
	for (i = 0; i < 1 << m; i++)
		if (f[n][i] < mi)
		{
			mi = f[n][i];
			k = i;
		}
	for (i = n; i >= 1; i--)
	{
		c[i] = g[i][k];
		x = g[i][k]; y = 1;
		while (x > 1)
		{
			f2 = false;
			while (x % b[y] == 0)
			{
				x = x / b[y];
				f2 = true;
			}
			if (f2)
				k = k ^ (1 << (y - 1));
			y++;
		}
	}
	for (i = 1; i < n; i++)
		cout << c[i] << ' ';
	cout << c[n] << '\n';
}

Another Sith Tournament

https://codeforces.com/contest/678/problem/E

#include<bits/stdc++.h>
using namespace std;
int n, i, j, k, l, b[1 << 19];
double a[20][20], f[1 << 19], ma;
int main()
{
	cin >> n;
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			cin >> a[i][j];
	for (i = 0; i < 1 << n; i++)
	{
		k = i; 
		while (k > 0)
		{
			b[i] = b[i] + k % 2;
			k = k / 2;
		}
	}
	f[1] = 1;
	for (i = 2; i <= n; i++)
		for (j = 0; j < 1 << n; j++)
			if (b[j] == i)
				for (l = 1; l <= n; l++)
					if (j & (1 << (l - 1)))
						for (k = 1; k <= n; k++)
							if (j & (1 << (k - 1)))
								if (k != l)
									f[j] = max(f[j], f[j ^ (1 << (l - 1))] * a[k][l] + f[j ^ (1 << (k - 1))] * a[l][k]);
	printf("%.6f", f[(1<<n)-1]);
}

Binary Table

https://codeforces.com/contest/662/problem/C

#include<bits/stdc++.h>
using namespace std;
int n, m, i, j, k, s, ma; char ch;
int a[22][100005], f[22][1 << 21];
int main()
{
	cin >> n >> m;
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
		{
			cin >> ch;
			a[i][j] = ch - '0';
		}
	for (i = 1; i <= m; i++)
	{
		s = 0; 
		for (j = 1; j <= n; j++)
			s = s * 2 + a[j][i];
		f[0][s]++;
	}
	for (i = 1; i <= n; i++)
		for (j = n; j >= 1; j--)
			for (k = 0; k < 1 << n; k++)
				f[j][k] = f[j][k] + f[j - 1][k ^ (1 << (i - 1))];
	ma = 1e10;
	for (i = 0; i < (1 << n); i++)
	{
		s = 0;
		for (j = 1; j <= n; j++)
			s =	s + f[j][i] * min(j, n - j);
		ma = min(ma, s);
	}
	cout << ma << '\n';
}

标签：std,int,状压,namespace,long,using,include,DP
From： https://www.cnblogs.com/ShadowAA/p/17320821.html

相关文章

  • 树形DP
    树形DP树形DP，即在树上进行的DP。由于树固有的递归性质，树形DP一般都是递归进行的。例题没有上司的舞会洛谷1352#include<bits/stdc++.h>usingnamespacestd;intn,i,x,y,b[6005],f[6005][2];vector<int>a[6005];voidsc(intx){ for(inti=0;i<a[x].size();i++) ......
  • 数位DP
    数位DP数位是指把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是0~9，其他进制可类比十进制。数位DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：要求统计满足一定条件的数的数量（即，最终目的为计数）；......
  • DP优化
    DP优化单调队列优化WatchingFireworksisFunCF372C#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;lln,m,d,i,j,k,l,r,ma,f[2][150005],g[150005],a[305],b[305],c[305];intmain(){ cin>>n>>m>>d; for(i=1;i<=m;i++) ......
  • 线性DP
    线性DP最长公共子序列O(n*m)写法inta[MAXN],b[MAXM],f[MAXN][MAXM];intdp(){for(inti=1;i<=n;i++)for(intj=1;j<=m;j++)if(a[i]==b[j])f[i][j]=f[i-1][j-1]+1;elsef[i][j]=std::max(f[i-1][j],......
  • 背包DP
    背包DP二进制分组优化考虑优化。我们仍考虑把多重背包转化成0-1背包模型来求解。预处理物品数量是2的次方。且要覆盖物品数量的点。即2n次方+1到kindex=0;for(inti=1;i<=m;i++){intc=1,p,h,k;cin>>p>>h>>k;while(k>c){k-=c;......
  • PyQt5 软件在 macOS HiDPI 模式下出现字体模糊的问题
    ​ Retina屏幕是苹果公司在2010年在 WWDC上发布的一种高密度像素的屏幕。HiDPI是一种渲染技术，它可以让Retina屏幕上的图像更加清晰。HiDPI技术会将图像渲染成两倍于原始分辨率的大小，然后再将其缩小到原始分辨率的大小，这样就可以让图像更加清晰。PyQt5编写的软件在Wi......
  • 计算机网络 传输层协议TCP和UDP
    目录一、传输层协议二、tcp协议介绍三、tcp报文格式四、tcp三次握手五、tcp四次挥手六、udp协议介绍七、常见协议和端口八、有限状态机  一、传输层协议传输层协议主要是TCP和UDP协议主要作用1.分段和重组2.会话多路复用 二、tcp协议......
  • 神策数据入选 IDC 中国客户数据平台 CDP 市场规模及厂商份额报告
    近日，IDC首发中国客户数据平台CDP市场规模及厂商份额报告，明确了CDP产品的功能和使用方式，以便减少购买者的困惑。IDC市场份额报告调研的厂商包括神策数据在内的15家企业，报告显示，市场前5家公司营业额几乎占整个市场的二分之一(47.1%)。报告中，IDC将CDP产品的主要功能分为......
  • 解决 dpkg 安装出错后的 Sub-process /usr/bin/dpkg returned an error code (1) 错误
    在使用dpkg-i安装.deb软件包的过程中，会出现安装失败的可能。之后无论用sudoaptinstall-forsudaptautoremove等常见的修复命令都是无效的。网络上很多解决方案都直接给出需要运行的命令，不分析原因也不说明理由。我从来不尝试这样的解决方案，除非我自己知道或是只能死马......
  • 【DP】【分治】LeetCode 53. 最大子数组和
    题目链接[https://leetcode.cn/problems/maximum-subarray/description/](53.最大子数组和"https://leetcode.cn/problems/maximum-subarray/description/")思路分析动态规划题目的时候只需要考虑最后一个阶段，因为所有的阶段转化都是相同的，考虑最后一个阶段容易发现规律在数......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99