[NOI2001] 炮兵阵地 （状压Dp经典例题）

时间：2023-03-09 03:53:43
[NOI2001] 炮兵阵地 （状压Dp经典例题）

　　如果您的电脑比较优秀能在 1sec 内跑过 2^1000 的时间复杂度，不妨你可以尝试一下，其实实际时间复杂度远远少于 2^1000，作为骗分不错的选择QAQ，然后我们来分析一下正解：

　　很显然此题是一题裸的状压Dp，一看数据范围就知道了，所以状态变得很显然了 f[i][j][k] 表示到第 i 层前一层是 j 上上层是 k 的最大炮兵数。

　　所以转移就很显然：f[i][j][k]=max{f[i-1][k][q]+Num[j]} (Num[j] 表示第 j 行的炮兵数)

　　显然时间复杂度变为了O(n*4^m*2^m)，如果评测机优秀凭借你完美的常数系统应该可以卡过，但实际上真的需要枚举 2^n 个状态嘛，显然是不需要，所以我们只需要枚举一些合法状态就可以了，令人惊讶的是每一层的合法状态竟然只有60种，所以我们的时间复杂度达到了优秀的 O(n*60^3)，舒服QWQ！！！

　　所以我们状态变为了：f[i][j][k] 表示第 i 行前一行是合法状态 j 上上行为合法状态 k 的最大炮兵数。

　　转移同上咯，自行领悟。（注意需要判断当前的合法状态是否符合当前的地形）。

　　随后附上我的完美代码QWQ：

　　

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<cstring>

 using namespace std;

 const int MAXN=;

 int Map[MAXN], Plan[MAXN], Num[MAXN], dp[MAXN][MAXN][MAXN];

 int N, m, cnt=, ans;

 inline int get_one(int i){

     int sum=;

     for (int x=i; x; x-=x & (-x)) sum++;

     return sum;

 }

 int main(){

     scanf("%d%d", &N, &m);

     for (int i=; i<=N; i++){

         char st[];

         scanf("%s", st+);

         int len=strlen(st+);

         for (int j=; j<=len; j++)

             if (st[j]=='H') Map[i]+=(<<j-);

     }      //记录当前行的地形

     for (int i=; i<(<<m); i++){

         if ((!((i<<)&i)) && (!((i>>)&i)) && (!((i<<)&i)) && (!((i>>)&i))){

             cnt++;

             Plan[cnt]=i;

             Num[cnt]=get_one(i);      //预处理当前行有几个炮兵

             if (!(Map[] & Plan[cnt])) dp[][cnt][]=Num[cnt];      //预处理第一行的状态

         }

     }

     for (int i=; i<=cnt; i++)

         for (int j=; j<=cnt; j++)

             if ((!(Plan[i] & Plan[j])) && (!(Plan[j] & Map[])))

                 dp[][j][i]=max(dp[][i][]+Num[j], dp[][j][i]);

 //预处理第二行的状态

     for (int i=; i<=N; i++){

         for (int j=; j<=cnt; j++)

             if (!(Plan[j] & Map[i])){

                 for (int k=; k<=cnt; k++)

                     if (!(Plan[j] & Plan[k])){

                         for (int q=; q<=cnt; q++)

                             if (!(Plan[j] & Plan[q]) && !(Plan[q] & Plan[k]))

                                 dp[i][j][k]=max(dp[i][j][k], dp[i-][k][q]+Num[j]);

                     }

             }

     }

 //Dp转移

     for (int i=; i<=cnt; i++)

         for (int j=; j<=cnt; j++)

             ans=max(ans, dp[N][i][j]);

 //求最后一行的最值

     printf("%d\n", ans);

     return ;

 }

　　最后比较空的小伙伴可以去尝试一下，NOIP2016D2T3 愤怒的小鸟这一题，加油加油

　　

　　

相关文章