[bzoj2310] Park II 플러그 dp

1769 단어 동적 기획
독립된 플러그를 가진 dp는 상태를 4진수로 표시하는데 비트 연산 기교를 습득하는 것은 매우 느리지만...
#include
#include
#include
#include
#include
#include
#define maxn 100010
#define inf 1000000000

using namespace std;

int n,m,now,pre,num,ans;
int hash[2][maxn],head[10010],to[maxn],next[maxn],tot[2],f[2][maxn];
int a[110][110],bit[50];

void add(int s,int x)
{
	int pos=s%10000;
	for (int p=head[pos];p;p=next[p])
	  if (hash[now][to[p]]==s)
	  {
	  	f[now][to[p]]=max(f[now][to[p]],x);
	  	return;
	  }
	tot[now]++;
	hash[now][tot[now]]=s;
	f[now][tot[now]]=x;
	to[++num]=tot[now];next[num]=head[pos];head[pos]=num;
}

int find_pos(int s,int i)
{
	return (s/(1<=1;i--)
	{
		int p=find_pos(s,i);
		if (p==2) cnt++;
		else if (p==1) cnt--;
		if (!cnt) return i;
	}
}

int find_r(int s,int k)
{
	int cnt=0;
	for (int i=k;i<=m+1;i++)
	{
		int p=find_pos(s,i);
		if (p==1) cnt++;
		else if (p==2) cnt--;
		if (!cnt) return i;
	}
}

void dp()
{
	now=1;pre=0;
	tot[now]=1;
	hash[now][1]=0;
	f[now][1]=0;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=tot[now];j++) hash[now][j]<<=2;
		for (int j=1;j<=m;j++)
		{
			swap(now,pre);
			for (int k=1;k<=tot[now];k++) f[now][k]=-1;
			num=0;tot[now]=0;
			memset(head,0,sizeof(head));
			for (int k=1;k<=tot[pre];k++)
			{
				int s=hash[pre][k],num=f[pre][k]+a[i][j];
				if (s>=(1<

좋은 웹페이지 즐겨찾기