0x55~0x56

0x55~0x66

0x55~0x66
- 0x56 状压DP
  - a.[√] Mondriaan's Dream
  - b.[√]炮兵阵地
- 0x55 有后效性的DP处理
  - c.[√]Naptime
  - d[√].Broken Robot

0x56 状压DP

a.[√] Mondriaan's Dream

题目传送

sol:

注意到数据范围十分的小，考虑状态压缩。

依次考虑每一行，可以注意到这一行的方块分成两种：

① 横着填的方块中一块。

② 竖着填的方块中一块。

分析一下当前行对下一行的影响：当且仅当本行存在竖着填的那种方块中的上面那一块才会对下一行有影响。

所以把满足上面情况的位置记为1，其余位置记为0。

另外为了保证合法，必须保证除了竖着填占了的，剩下的连续的每一段0都是偶数。

这可以提前处理好，设合法集合位G。

那么转移为：

[f[i,j]=sum_{j&k 并且 j|kin G}{f[i-1,k]} ]

code:

#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define IL inline
#define LL long long
#define DB double
using namespace std;

const int N=13;
const int M=2049;

int n,m,ans,g[M];
LL f[N][M];

int main()
{
	RG int i,j,k,fl,cnt,all;
	while(scanf("%d%d",&n,&m)!=EOF&&n&&m) {
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		f[0][0]=1,all=1<<m;
		for(i=0;i<all;++i) {
			fl=cnt=0;
			for(j=0;j<m;++j)
				if((i>>j)&1) fl|=cnt,cnt=0;
				else cnt^=1;
			g[i]=!(fl|cnt);
		}
		for(i=1;i<=n;++i)
			for(j=0;j<all;++j)
				for(k=0;k<all;++k)
					if(!(j&k)&&g[j|k])
						f[i][j]+=f[i-1][k];
		printf("%lld
",f[n][0]);
	}
    return 0;
}

b.[√]炮兵阵地

题目传送

sol:

首先可以把一行行的合法情况预处理出来，记为G。

然后把最大的数据输进去测一下发现最多也就只有60种情况，比起1048小了很多。

接着考虑竖直上的，发现影响了上(下)两行，那么记录连续两行即可。

接下来是无脑转移了。

那么复杂度(O(n*G^3))。

code:

#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define IL inline
#define LL long long
#define DB double
using namespace std;

const int N=103;
const int M=1025;

char s[N];
int n,m,tot,ans,g[M],a[N],b[N],f[N][N][N];

IL bool check(int x) {
	if((x>>1)&x||(x>>2)&x||(x<<1)&x||(x<<2)&x) return 0;
	return 1;
}

IL int calc(int x) {
	RG int cnt=0;
	for(;x;x>>=1) cnt+=x&1;
	return cnt;
}

int main()
{
   	RG int i,j,k,p,all;
	scanf("%d%d",&n,&m),all=1<<m;
	for(i=0;i<all;++i)
		if(check(i)) g[++tot]=i;
	for(i=1;i<=tot;++i) b[i]=calc(g[i]);
	for(i=1;i<=n;++i) {
		scanf("%s",s);
		for(j=0;j<strlen(s);++j)
			if(s[j]=='H') a[i]|=1<<j;
	}
	for(i=1;i<=tot;++i) f[1][i][1]=b[i];
	for(i=2;i<=n;++i)
		for(j=1;j<=tot;++j)
			if(!(g[j]&a[i]))
				for(k=1;k<=tot;++k)
					if(!(g[k]&a[i-1])&&!(g[j]&g[k]))
						for(p=1;p<=tot;++p)
							if(!(g[p]&a[i-2])&&!(g[j]&g[p])&&!(g[k]&g[p]))
								f[i][j][k]=max(f[i][j][k],f[i-1][k][p]+b[j]);
	for(i=1;i<=tot;++i)
		for(j=1;j<=tot;++j) ans=max(ans,f[n][i][j]);
	printf("%d
",ans);
    return 0;
}

0x55 有后效性的DP处理

c.[√]Naptime

题目传送

sol:

不难考虑设(f[i,j,0/1])表示前i个小时，睡了j小时，第i小时不在(在)睡的最大体力值。

那么转移应该为：

[f[i,j,0]=max{f[i-1,j,0],f[i-1,j,1]}\ f[i,j,1]=max{f[i-1,j-1,0],f[i-1,j-1,1]+a[i]} ]

但是由于这个时间是连续的，所以转移似乎找不到一个起点。

所以不妨钦定一个起点开始转移，若定为1，则第1个小时必然不能获得体力。

所以初始化(f[1,0,0]=f[1,1,1]=0)，进行转移，最后(ans1=max{f[n,B,0],f[n,B,1]})。

但是这样的话就强制了第1个小时没休息，所以还需要补上n点到1点间休息且第1个小时也休息的情况。

此时初始化(f[1,1,1]=a[i])即可，最后(ans2=f[n,B,1])。

二者取较大值即为最后的答案。

code:

#include<bits/stdc++.h>
#define RG register
#define IL inline
#define LL long long
using namespace std;

IL int gi() {
    RG int x=0,w=0; char ch=0;
    while(ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return w?-x:x;
}

const int N=4010;

int n,B,ans,rt[N],f[N][N][2];

int main ()
{
    RG int i,j,T=gi();
    while(T--) {
        n=gi(),B=gi();
        for(i=1;i<=n;++i) rt[i]=gi();
        memset(f,0xcf,sizeof(f));
        f[1][1][1]=f[1][0][0]=0;
        for(i=2;i<=n;++i)
            for(j=0;j<=i;++j) {
                f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]);
                if(j>0) f[i][j][1]=max(f[i-1][j-1][0],f[i-1][j-1][1]+rt[i]);
            }
        ans=max(f[n][B][0],f[n][B][1]);
        memset(f,0xcf,sizeof(f));
        f[1][1][1]=rt[1];
        for(i=2;i<=n;++i)
            for(j=0;j<=i;++j) {
                f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]);
                if(j>0) f[i][j][1]=max(f[i-1][j-1][0],f[i-1][j-1][1]+rt[i]);
            }
        printf("%d
",max(ans,f[n][B][1]));
    }
    return 0;
}

d[√].Broken Robot

题目传送

sol:

设(f[i,j])表示从i,j走到最后一行，所需要的步数的期望。

由于存在四种操作，不难列出转移：

[f[i,j]=frac{1}{4}{f[i,j-1]+f[i,j+1]+f[i,j]+f[i+1,j]}+1 ]

对于边界条件特殊考虑，此处不列出。

可以发现这个转移存在有后效性，是无法进行的。

但是行与行之间却是满足无后效性，只能由i+1行转移到i行。

所以可以由n到1一行行考虑，然后再具体解每一行：

首先对于当前行的每一个位置，都有一个方程，共m个。

然后由于当前行的下一行已经求解完毕，所以总共也只有m个未知量。

所以可以用高斯消元把DP值直接求解出来。

这样就只需要对转移式子进行移项得到系数即可。

code：

#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define IL inline
#define LL long long
#define DB double
using namespace std;

IL int gi() {
   RG int x=0,w=0; char ch=getchar();
   while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();}
   while (ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
   return w?-x:x;
}

const int N=1003;

int n,m,x,y;
DB f[N][N],g[N][N];

IL void build(int i) {
	if(m==1) {
		g[1][1]=-0.5,g[1][2]=-0.5*f[i+1][1]-1;
		return;
	}
	RG int k;
	g[1][1]=g[m][m]=-2.0/3.0,g[1][2]=g[m][m-1]=1.0/3.0;
	g[1][m+1]=-1.0/3.0*f[i+1][1]-1,g[m][m+1]=-1.0/3.0*f[i+1][m]-1;
	for(k=2;k<m;++k) 
		g[k][k-1]=g[k][k+1]=0.25,g[k][k]=-0.75,g[k][m+1]=-0.25*f[i+1][k]-1;	
}

IL void gauss(int R) {
	RG int i;
    for(i=1;i<m;i++) {
        double RT=g[i+1][i]/g[i][i];
        g[i+1][i]-=RT*g[i][i];
        g[i+1][i+1]-=RT*g[i][i+1];
        g[i+1][m+1]-=RT*g[i][m+1];
    }
    f[R][m]=g[m][m+1]/g[m][m];
    for (i=m-1;i>=1;i--) f[R][i]=(g[i][m+1]-f[R][i+1]*g[i][i+1])/g[i][i];
}
 
int main()
{
	RG int i;
   	n=gi(),m=gi(),x=gi(),y=gi();
	for(i=n-1;i>=x;--i) build(i),gauss(i);
	printf("%.10lf
",f[x][y]);
    return 0;
}
//高斯消元解局部有后效性的DP