C++ 洛谷 P2704 [NOI2001]炮兵阵地

P2704 [NOI2001]炮兵阵地

没学状压DP的看一下

此题意思很简单，如下图，就是十字架上的不能有两个点放炮兵。

在做此题前，先做一下玉米田

玉米田题解

分析：

而m即一行的个数小于等于10，每个格子上只有防或不放两种情况

很自然就会想到状压DP

还有一点很重要：

要符合题目条件的只有平原可以放炮兵。

所以还要匹配炮兵放法与平原的关系（一共要判断3种，PH，列列列，横横横）。

如下是DP思考过程：（和玉米田差不多）

我们需要考虑定义，我们可以定义dp[i][j][k]表示到第i行状态为j,且上一行状态为k时的最大方案数

然后我们要来考虑初始化，因为状态肯定由前两行推过来，所以我们需要单独处理第一二行的方案数

取最大的话就一定要和原来的自己、前一个状态+增长比较，取较大的那个

最后还有一个问题，数组dp[105][1024][1024]!!!!这空间超400MB啊！

所以还得优化空间。

滚动数组:因为当前状态只与前两行有关，所以只需保留有用的三行

dp[105][1024][1024] --> dp[3][1024][1024] 好很多了（已经不爆了，但我们要做到最优，这是OIer的信念）

预处理:实际上没有几种情况是可以满足横排的（m = 10时，70个不到），于是我们就可以把这些满足条件的保存下来。~~~

dp[3][1024][1024] --> dp[3][70][70]

代码：

#include<cstdio>

#include<iostream>

using namespace std;

const int maxn=;

int n,m;

int st[],sum[];

int cnt;

int dp[][][];

int map[maxn];

int ans=;

void init(int s,int tot,int i)

{

    if(i>=m)

    {

        st[++cnt]=s;

        sum[cnt]=tot;

        //printf("st=%d sum=%d\n",st[cnt],sum[cnt]);

        return;

    }

    init(s,tot,i+);

    init(s+(<<i),tot+,i+);

}

void add()

{

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

    {

        //printf("st=%d map=%d ",st[i],map[0]);

        if(!(map[]&st[i]))

        {

            dp[][i][]=sum[i];

            //printf("%d\n",dp[1][i][0]);

        }

        //printf("sum=%d %d\n",sum[i],dp[0][i][0]);

    }

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

      {

          if(!(st[i]&map[]))

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

          if((!(st[j]&map[]))&&(!(st[i]&st[j])))

          {

             dp[][i][j]=sum[i]+sum[j];

             //printf("i=%d j=%d %d\n",st[i],st[j],dp[2][i][j]);

        }

    }

}

void come_dp()

{

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

    {

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

        {

            if(!(st[j]&map[i]))

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

            if((!(st[k]&map[i-]))&&(!(st[k]&st[j])))

            {

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

                if((!(st[u]&map[i-]))&&(!(st[u]&st[j]))&&(!(st[u]&st[k])))

                dp[i%][j][k]=max(dp[i%][j][k],dp[(i-)%][k][u]+sum[j]);

            }

        }

    }

}

void work()

{

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

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

    {

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

    {

        char x;

        cin>>x;

        map[i]<<=;

        if(x=='H') map[i]+=;

    }

    }

    //printf("%d\n",map[1]);

    init(,,);

    add();

    come_dp();

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

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

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

    printf("%d",ans);

}

int main()

{

    work();

    return ;

}

逃qaq

巴特西

C++ 洛谷 P2704 [NOI2001]炮兵阵地

最新文章

热门文章