NOI2001D2T1 | 炮兵阵地

Portal

炮兵的攻击范围是上下左右 2 格,那么显然应以行为阶段,以该行的放置情况和上行的情况作为状态。直接出状态转移方程:
fi,j,k=max{fi1,k,t+cj}f_{i,j,k}=\max{f_{i-1,k,t}+c_j}

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
#include <cstdio>
#include <algorithm>
int ans,g[101],s[77],c[77],f[101][77][77];
int main() {
int n,m,ed;char tmp[11];
scanf("%d%d",&n,&m);ed=1<<m;
for(int i=1;i<=n;++i) {
scanf("%s",tmp);
for(int j=0;j<m;++j) g[i]|=((tmp[j]=='H')<<j);
}
for(int i=0,cnt=1;i<ed;++i,cnt=1) {
for(int j=1;j<ed;j<<=1) if(i&j)
if(i&(j<<1)||i&(j<<2)) {cnt=0;break;} else ++cnt;
if(cnt) {s[++s[0]]=i;c[s[0]]=cnt-1;}
}
for(int j=1;j<=s[0];++j) if(!(g[1]&s[j])) f[1][j][1]=c[j];
for(int j=1;j<=s[0];++j) if(!(g[2]&s[j]))
for(int k=1;k<=s[0];++k) if(!(s[j]&s[k]||g[1]&s[k]))
f[2][j][k]=f[1][k][1]+c[j];
for(int i=3;i<=n;++i)
for(int j=1;j<=s[0];++j)
if(!(g[i]&s[j]))
for(int k=1;k<=s[0];++k)
if(!(g[i-1]&s[k]||s[j]&s[k]))
for(int t=1;t<=s[0];++t)
if(!(g[i-2]&s[t]||s[j]&s[t]||s[k]&s[t])) {
f[i][j][k]=std::max(f[i][j][k],f[i-1][k][t]+c[j]);
ans=std::max(ans,f[n][j][k]);
}
printf("%d",ans);
return 0;
}

Download

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。