【[GDOI2014]拯救莫莉斯】

可能我的状态比较鬼畜，应该没有人这么写

设\(dp[i][j][k]\)表示在第\(i\)行，放置油库的状态为\(j\)，实际上周围已经有油库或者本身有油库的状态为\(k\)的时候的最小花费

由于我们是按照行来\(dp\)的，所以这里的周围有油库只有三种可能

上一行的这个位置有油库
这个位置本身有油库
同一行上相邻位置有油库

显然如果上一行的某一个状态里，有一些位置周围没有油库，那么就说明接下来这一行的对应位置就必须都放上油库，其余剩下的位置可以放油库也可以不放

于是我们可以枚举子集进行转移

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#define re register

#define lowbit(x) ((x)&(-x))

#define min std::min

int n,m;

int map[51][51];

int dp[51][129][129],s[51][129][129];

int val[51][129],num[129];

inline int read()

{

	char c=getchar();

	int x=0;

	while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9')

		x=(x<<3)+(x<<1)+c-48,c=getchar();

	return x;

}

inline int logg(int x)

{

	int tot=0;

	while(x) tot++,x>>=1;

	return tot;

}

inline int cnt(int x)

{

	int tot=0;

	while(x) tot++,x-=lowbit(x);

	return tot;

}

int M;

inline int solve(int x)

{

	return M&(((x<<1)|x)|((x>>1)|x));

}

inline void merge(int a,int b,int c,int v,int t,int x,int y,int z)

{

	if(dp[a][b][c]+v>dp[x][y][z]) return;

	if(dp[a][b][c]+v<dp[x][y][z])

	{

		dp[x][y][z]=dp[a][b][c]+v;

		s[x][y][z]=s[a][b][c]+t;

		return;

	}

	s[x][y][z]=min(s[x][y][z],s[a][b][c]+t);

}

int main()

{

	n=read(),m=read();

	for(re int i=1;i<=n;i++)

		for(re int j=1;j<=m;j++)

			map[i][j]=read();

	M=(1<<m)-1;

	for(re int i=1;i<=n;i++)

		for(re int j=1;j<=M;j++)

			val[i][j]=val[i][j-lowbit(j)]+map[i][logg(lowbit(j))];

	for(re int i=1;i<=M;i++) num[i]=cnt(i);

	memset(dp,20,sizeof(dp));

	for(re int i=0;i<=M;i++)

		dp[1][i][solve(i)]=min(dp[1][i][solve(i)],val[1][i]),s[1][i][solve(i)]=num[i];

	for(re int i=2;i<=n;i++)

	{

		for(re int j=0;j<=M;j++)

		{

			int p=M^j;

			for(re int k=p;k;k=(k-1)&p)

			{

				if(dp[i-1][j][k|j]==336860180) continue;

				int d=k|j,s=M^d;

				for(re int t=d;t;t=(t-1)&d)

					merge(i-1,j,d,val[i][s]+val[i][t],num[s]+num[t],i,t|s,j|solve(t)|solve(s));

				merge(i-1,j,d,val[i][s],num[s],i,s,j|solve(s));

			}

			for(re int k=0;k>-1;k--)

			{

				if(dp[i-1][j][k|j]==336860180) continue;

				int d=k|j,s=M^d;

				for(re int t=d;t;t=(t-1)&d)

					merge(i-1,j,d,val[i][s]+val[i][t],num[s]+num[t],i,t|s,j|solve(t)|solve(s));

				merge(i-1,j,d,val[i][s],num[s],i,s,j|solve(s));

			}

		}

	}

	int ans=999999999;

	for(re int i=0;i<=M;i++)

		ans=min(ans,dp[n][i][M]);

	int T=999999999;

	for(re int i=0;i<=M;i++)

	if(dp[n][i][M]==ans) T=min(T,s[n][i][M]);

	printf("%d %d\n",T,ans);

	return 0;

}

巴特西

【[GDOI2014]拯救莫莉斯】

最新文章

热门文章