首页 > 代码库 > NOI2001 炮兵阵地

NOI2001 炮兵阵地

2024-09-06 02:20:40   209人阅读

一道非常有意思的题目 很久之前考过 但那时候好像只会打裸搜索（捂脸跑

后来看题解的时候也是没有学状压的所以算是闲置了很久没动的题

昨天看到的时候第一反应是m<=10所以压m然后跑1-n枚举每一行

但是非常遗憾的是我一直在想横行怎么判断合法 所以比较sb的我想了好久都没想出来

于是又很怂逼地去看了题解（我怎么这么怂

横行合法只要位移然后与一下就可以判断了 竖行的合法就是根据上面两行的状态转移

f[i][j][k]表示的是第i行上一行状态为j本行状态为k的炮塔数量

特别注意零也是一种情况！！！昨天被坑了今天又被坑了TAT

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<string>
 7 using namespace std;
 8 int g[200],f[200][200][200],b[200],sum[200];
 9 bool pd(int x){//横行是否合法
10     if (x&(x<<1)) return 0;
11     if (x&(x<<2)) return 0;
12     return 1;
13 }
14 int w(int x){//判断此状态炮塔个数
15     int sum=0;
16     for (int l=x;l;l>>=1){
17         if (l&1) sum++;
18     }
19     return sum;
20 }
21 int main(){
22     memset(f,255,sizeof(f));
23     int n,m;
24     scanf ("%d%d",&n,&m);
25     for (int i=1;i<=n;++i)
26         for (int j=1;j<=m;++j){
27             char ch;
28             cin>>ch;
29             if (ch==‘H‘) g[i]|=1<<j-1;//记录是否可放
30         }
31     int tot=0;
32     for (int i=0;i<=(1<<m)-1;++i) if (pd(i)) b[++tot]=i,sum[tot]=w(i);//！！0也是一种放法！！
33     for (int i=1;i<=tot;++i) if (!(g[1]&b[i])) f[1][1][i]=sum[i];
34     for (int i=2;i<=n;++i)
35         for (int j=1;j<=tot;++j){
36             if (!(b[j]&g[i])){//此行可以放
37                 for (int k=1;k<=tot;++k){
38                     if (!(b[k]&b[j])){
39                         for (int l=1;l<=tot;++l)
40                             if (!(b[l]&b[j])){//前两行无影响
41                                 if (f[i-1][l][k]!=-1) f[i][k][j]=max(f[i][k][j],f[i-1][l][k]+sum[j]);//转移
42                             }
43                     }
44                 }
45             }
46         }
47     int ans=-1;
48     for (int i=1;i<=tot;++i) for (int j=1;j<=tot;++j) ans=max(ans,f[n][i][j]);
49     cout<<ans;
50     return 0;
51   }

 

NOI2001 炮兵阵地


联系
我们