【BZOJ 4626】[BeiJing2016] 空袭

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4626
数据生成器：http://paste.ubuntu.com/23171656/

这题，是我到目前为止做过的最恶心的题目
没有之一

如果击中，那么三级狗一定在连续$a_i$个回合里没有转向，并且有一个回合没有动
那么$DP$的时候记录一下最近$a_i$次的移动情况即可
chenyushuo提供的资料：http://pan.baidu.com/s/1kVg3uvl

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

const int MOD = 1000000007;

int X,Y,OP,n,m,T,vis[30][30],hit[60][13][13],f[2][22][22][5][21][13],W=1,P;
int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1},vout[22][22],del[60];
char pat[30];

int main(){
	cin>>n>>m>>T; 
	for (int i=1;i<=n;i++) {
		scanf("%s",pat+1);
		for (int j=1;j<=m;j++) 
			if (isdigit(pat[j])) vis[i][j] = 1, f[P][i][j][pat[j]-'0'+1][0][0] = 1;
			else if (pat[j] == '.') vis[i][j] = 1;
	} 
	for (int i=1;i<T;i++) cin>>del[i];
	for (int k=0;k<=T;k++) for (int go=0;go<=12;go++) for (int dly=0;dly<=go;dly++)
		for (int w=dly;w<go;w++) if (k-w >= 1 && del[k-w] == w+1) hit[k][go][dly] = 1;
	for (int k=1;k<=T;k++,W^=1,P^=1,memset(f[W],0,sizeof(f[W]))) for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) 
		if (vis[i][j]) for (int to=1;to<=4;to++) for (int go=0;go<=12;go++) for (int dl=0,tmp;dl<=12;dl++) {
			if (!(tmp=f[P][i][j][to][go][dl])) continue;
			if (!hit[k-1][dl][0]) (f[W][i][j][to][min(12,dl+1)][0] += tmp) %= MOD;
			if (vis[i+dx[to]][j+dy[to]] && !hit[k-1][go][dl]) 
				(f[W][i+dx[to]][j+dy[to]][to][min(12,go+1)][min(12,dl+1)] += tmp) %= MOD;
			for (int op=1;op<=4;op++) if (op != to && vis[i+dx[op]][j+dy[op]]) 
				(f[W][i+dx[op]][j+dy[op]][op][0][0] += tmp) %= MOD;
	}
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) for (int to=1;to<=4;to++) 
		for (int go=0;go<=12;go++) for (int dl=0;dl<=12;dl++) 
			(vout[i][j] += f[P][i][j][to][go][dl]) %= MOD;
	for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) 
		printf("%d%c",vout[i][j],j==m?'\n':' ');
	return 0;
}