COCI2011/2012 Contest#1 F 状压加速dp

首先是一个非常Naive的dp，令$dp[i][x][y]$表示$i$时刻$x,y$是否能被跳到

枚举，然后转移，如果滚动数组，就可以做到$O(n^2)$空间，$O(Tn^2)$时间复杂度

这显然是TLE的。。。

注意到题目的$n\leq 30$，可以直接用一个int存在某一行/列的答案

设时刻$i$第$j$列的答案为$dp[i][j]$

假设不考虑答案的限制，两之间转移可以做到$O(1)$，即

1.$dp[i][j\pm 1]$左/右移两位

2.$dp[i][j\pm 2]$左/右移一位

两者转移即可，但是涉及到倍数的限制，设$can[i][j]$为$i$时刻$j$列的可行跳跃位置

则只需要最后的时候让$dp[i][j]$与$can[i][j]$取交集即可

如果直接枚举倍数，复杂度上限是$O(n^2 T)$

考虑分块决策，设将$[1,D]$的因数挑出来额外记录一个数组$can2[x][j]$表示值为$x$的第$j$列有那些

不直接枚举他们，而是在每次访问时考虑他们对于$can[i][j]$的贡献

在优秀实现下，复杂度上限为$O(n^2\frac{T} {D+1}+T (D+\sum_{t=1}^{D} \frac{1} {t} n))=O(n^2\frac{T} {D+1}+T (n\ln D+D))$

这个实现上来说，就是枚举时间$i$后，判断是否满足$t|i $，然后再将$can2[t][j]$贡献到$can[i][j]$

显然，$t|i$成立的次数就是$T\sum_{t=1}^{D} \frac{1} {t} $，也就是要循环这么多次取贡献$j$这一维

调整一下$D$的参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define reg register
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)
const int N=30,D=7;

int n,m,a[N][N],dp[2][N];
int can[1000010][N],t[D+1][N];

int main(){
	scanf("%d%d",&n,&m);
	int sx,sy; scanf("%d%d",&sx,&sy),sx--,sy--;
	rep(i,0,n-1) rep(j,0,n-1) {
		scanf("%d",&a[i][j]);
		if(a[i][j]<=D) t[a[i][j]][i]|=1<<j;
		else for(reg int T=a[i][j];T<=m;T+=a[i][j]) can[T][i]|=1<<j;
	}
	int cur=0; dp[cur][sx]=1<<sy;
	rep(i,1,m) {
		rep(j,1,D) if(i%j==0) rep(k,0,n-1) can[i][k]|=t[j][k];
		rep(j,0,n-1) {
			dp[!cur][j]=0;
			if(j) {
				dp[!cur][j]|=dp[cur][j-1]<<2;
				dp[!cur][j]|=dp[cur][j-1]>>2;
			}
			if(j<n-1) {
				dp[!cur][j]|=dp[cur][j+1]<<2;
				dp[!cur][j]|=dp[cur][j+1]>>2;
			}
			if(j>1) {
				dp[!cur][j]|=dp[cur][j-2]<<1;
				dp[!cur][j]|=dp[cur][j-2]>>1;
			}
			if(j<n-2) {
				dp[!cur][j]|=dp[cur][j+2]<<1;
				dp[!cur][j]|=dp[cur][j+2]>>1;
			}
			dp[!cur][j]&=can[i][j];
		}
		cur^=1;
	}
	int ans=0;
	rep(i,0,n-1) rep(j,0,n-1) if(dp[cur][i]&(1<<j)) ans++;
	printf("%d\n",ans);
	rep(i,0,n-1) rep(j,0,n-1) if(dp[cur][i]&(1<<j)) printf("%d %d\n",i+1,j+1);
}