통형 압도 dp 학습 노트

요약:

상태 압축은 매우 광범위한 개념(hash를 포함해도 상태 압축의 일종?)이다.dp를 사용하면 디지털 dp와 같이 2진법이나 n진법으로 하나의 상태를 표시하여 상태를 표시하기도 편리하고 옮기기도 편리하다.그리고 만악의 위운산으로 문제의 뜻에 부합되는지 판단하고 O(1)의 이동을 실현할 수 있다.일반적으로 모든 단행의 합법적인 상태를 미리 처리하고 dfs(n/이진법하) 또는 직접 매거진(이진법하)을 통해 실현할 수 있다.상압 dp가 요구하는 비트(바둑판 너비)는 너무 크면 안 된다. 그렇지 않으면 상태가 너무 많으면 차가워진다.
(비트 연산을 잊어버리면 외출 시 좌회전:https://baike.baidu.com/item/비트 연산/6888804?fr=aladdin)

loj#10170. 원권 통 5.4례 1 기사

https://loj.ac/problem/10170원제는 서로 침범하지 않는 킹이다. 먼저 폭력매가 모든 1의 좌우에 1이 없는 상태를 들고, 각 줄마다 한 줄을 드는 합법적인 상태를 직접 계승한다. 사실 일반 dp보다 1차원 상태가 많다.

#include 
#include 
#include 
using namespace std;
struct node
{
	int x,c;
	node()
	{
		x=0;c=0;
	}
}a[(1<<10)+10];
long long f[11][110][(1<<10)+10];//f[  ][    ][     ]
int n,kk,len,bin[11];
void dp()
{
	int mx=(1<

loj#10171. 목장의 안배

https://loj.ac/problem/10171가령 모든 가능한 상태를 먼저 찾아내서 일일이 열거할 때 풀을 심을 수 없는 곳에 풀을 심었는지 판단해 보세요. 몇 위인지 주의해서 생각해 보세요.

#include 
#include 
#include 
using namespace std;
#define LL long long
struct node
{
	int x,c;
}a[(1<<12)+10];
LL f[13][(1<<12)+10],ans;
int v[13][13],bin[13],len,n,m; 
void dp()
{
	int mx=(1<

loj#10172. '한 권 통5.4연습1'잼 바르기

https://loj.ac/problem/101723진 상태, 0 빨간색 잼, 1 녹색 잼, 2 파란색 잼은 dfs로 가능한 모든 상태를 찾아내고 잼을 바른 줄을 처리해야 한다. 다른 상태가 있을 수 없지만 계승 상태가 될 수 있다.

#include 
#include 
#include 
using namespace std;
#define LL long long
#define mod 1000000
int bin[11],p[110],len,n,m,a[10],ai;
LL f[11000][250];
void dfs(int l,int last,int s)
{
	if (l==0) {p[++len]=s;return ;}
	for (int i=0;i<=2;i++)
	{
		if (i==last) continue;
		dfs(l-1,i,s*3+i);
	}
}
bool check(int x,int y)
{
	for (int i=1;i<=m;i++)
	{
		int xx=x%3,yy=y%3;
		if (xx==yy) return 0;
		x/=3;y/=3;
	}
	return 1;
}
void dp()
{
	for (int k=2;k<=n;k++)
	{
		//if (k==ai) continue;
		for (int i=1;i<=len;i++)
		{
			for (int j=1;j<=len;j++)
			{
				if (check(p[i],p[j])&&f[k][p[i]]!=-1&&f[k-1][p[j]]!=-1) f[k][p[i]]=(f[k][p[i]]+f[k-1][p[j]])%mod;
			}
		}
	}
}
int main()
{
	bin[1]=1;
	for (int i=2;i<=10;i++) bin[i]=bin[i-1]*3;
	scanf("%d%d%d",&n,&m,&ai);
	int tt=0;
	for (int i=1;i<=m;i++) {scanf("%d",&a[i]);tt=tt*3+a[i]-1;}
	dfs(m,-1,0);
	for (int i=1;i<=len;i++) f[ai][p[i]]=-1;
	if (ai!=1) 
	{
		for (int i=1;i<=len;i++) f[1][p[i]]=1;
		f[ai][tt]=0;
	}
	else f[ai][tt]=1;
	dp();
	LL ans=0;
	for (int i=1;i<=len;i++) if (f[n][p[i]]!=-1) ans=(f[n][p[i]]+ans)%mod;
	printf("%lld
",ans%mod);
	return 0;
}

loj#10173. 포병 진지

무서워하지 마. T 떨어져!실제로 실행 가능한 상태수는 그렇게 많은 세 줄 상태를 일일이 열거하지 않고 직접 계승할 수 있다. i jk 모두 체크를 할 필요가 없다. 체크라는 줄만 있으면 된다. 만약에 지난 줄의 상태가 성립되지 않는다면 그의 f는 값이 없다. 그렇지 않으면 너는 가진 M만큼 큰 상수를 가지고 T를 떨어뜨리는 것과 같다는 것을 알 수 있다.RE/MLE 조심하고 스크롤 배열 켜기

#include 
#include 
#include 
using namespace std;
struct node
{
	int x,c;
}p[1100]; int len;
long long f[5][1100][1100]; //     f[][     ][     ]
int v[110][11],n,m,bin[11],now,pre;
char ch[11];
bool check(int x,int k)
{
	if (k==0) return 1;
	for (int i=1;i<=m;i++)
		if ((x&bin[i])!=0&&v[k][m-i+1]==0) return 0;
	return 1;
}
void dp()
{
	int mx=(1<

loj#10174. 동물원

https://loj.ac/problem/10174매번 매거 위치 1~5의 상태, 뒤에 있는 i~i+4 앞에 있는 i~i+3은 반드시 앞과 같아야 한다. 그러면 바로 max를 하고 마지막에 0/1의 상태를 계승하여 매거 f[0]의 상태를 계승한다. 첫 줄부터 f[1]가 f[0]로 출시된 것을 보증하고 f[n]=f[0]로 하여금 1과 n이 연결된 이 문제를 반대로 편리하게 한다. 즉, 고리를 펼치면 1이 대응하는 것이 가장 낮은 위치이다.n은 최고위, 만악에 대응하는 비트 연산이 정말 편해요.
사고&문제풀이:https://blog.csdn.net/qq_35914587/article/details/80228260 https://blog.csdn.net/lych_cys/article/details/51553437

#include 
#include 
#include 
using namespace std;
struct kids
{
	int x,f,l,fer,lov;
	kids()
	{
		x=f=l=fer=lov=0;
	}
}kid[51000];
int bin[10],n,c,f[11000][40];//f[ i   ][i~i+4       ] 1:    0:   
int s[11000][40];
int dp()
{
	int mx=(1<<5)-1,ans=0;
	for (int i=0;i<=mx;i++)
	{
		memset(f[0],-63,sizeof(f[0]));
		f[0][i]=0; //       
		for (int j=1;j<=n;j++)//       
		{
			for (int k=0;k<=mx;k++)
			{
				//int last=k; if ((last&bin[5])!=0) last-=bin[5]; last=(last<<1);        sd       ？    &((1<<4)-1)       
				//      ！ （            ） x&1==x%2， x|1==x+1
				f[j][k]=max(f[j-1][((k&15)<<1)|1],f[j-1][(k&15)<<1])+s[j][k];
			}
		}
		ans=max(ans,f[n][i]);//       
	}
	return ans;
}
int main()
{
	//freopen("1.in","r",stdin);
	bin[1]=1;
	for (int i=2;i<=5;i++) bin[i]=bin[i-1]<<1;
	scanf("%d%d",&n,&c);
	int mx=(1<<5)-1;
	for (int i=1;i<=c;i++)
	{
		scanf("%d%d%d",&kid[i].x,&kid[i].f,&kid[i].l);
		for (int j=1;j<=kid[i].f;j++) 
		{
			int x;
			scanf("%d",&x); x=(x-kid[i].x+n)%n+1;
			kid[i].fer=(kid[i].fer|bin[x]);
		}
		for (int j=1;j<=kid[i].l;j++)
		{
			int x;
			scanf("%d",&x); x=(x-kid[i].x+n)%n+1;
			kid[i].lov=(kid[i].lov|bin[x]);
		}
		for (int j=0;j<=mx;j++)	
		{
			//~ (   )：0 1 1 0 
			if (((~j)&kid[i].fer)!=0||(j&kid[i].lov)!=0) s[kid[i].x][j]++;
		}
	}
	printf("%d
",dp());
	return 0;
}

끝. 꽃 뿌려!나의 수학 선생님은 나를 3년 동안 속였는데, 어떤 사람은 쉬워도 나는 쉬워도 마음은 더욱 섬세하다. 분명히 사람은 어려워도 나는 어렵고, 사람은 쉬워도 나는 어렵다.