状态压缩dp求调

P2704 [NOI2001] 炮兵阵地

Violet___Evergarden @ 2021-09-20 10:17:41


#include <iostream>
#include <climits>
using namespace std;
const int kMaxN=101;
const int kMaxM=11;
int dp[kMaxN][1<<10][1<<10];//dp[i][j][k]为第i行，这一行为j,上一行为k时能放多少个
int n,m;
int mp[kMaxN][kMaxM],ans;
int zk[kMaxN];
int cnt;
struct CAN
{
  int zt,num;
}can[1<<10];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
  zk[i]=0;
  for(int j=1;j<=m;j++)
  {
    char a;
    cin>>a;
    mp[i][j]=(a=='P'?1:0);//放部队代表1，不放代表0
    zk[i]=(zk[i]<<1)+mp[i][j];//算每一行的平原的状态
  }
}
for(int i=1;i<=(1<<m)-1;i++)
{
  if(i&(i<<1))continue;//判断这种放法是否不行（即左边或右边2个格子放了）
  if(i&(i<<2))continue;
  if(i&(i>>1))continue;
  if(i&(1>>2))continue;
  can[++cnt].zt=i;
  int z=i;
  while(z)//算出这种情况放了几个
  {
    if(z&1)
    {
      can[cnt].num++;
    }
    z>>=1;
  }
}
for(int i=1;i<=cnt;i++)//特殊处理第一行
{
  if((can[i].zt&zk[1])!=can[i].zt)continue;//判断山地有没有放
  dp[1][i][0]=can[cnt].num;
}
for(int i=1;i<=cnt;i++)//特殊处理第二行
{
  if((can[i].zt&zk[1])!=can[i].zt)continue;
  for(int j=1;j<=cnt;j++)
  {
    if((can[j].zt&zk[2])!=can[j].zt)continue;
    if((can[i].zt&can[j].zt))continue;
    dp[2][j][i]=can[i].num+can[j].num;
  }
}
for(int i=3;i<=n;i++)//处理3~n行
{
  for(int j=1;j<=cnt;j++)//枚举上上行的状态
  {
    if((can[j].zt&zk[i-2])!=can[j].zt)continue;
    for(int k=1;k<=cnt;k++)//枚举上行的转台
    {
      if((can[k].zt&zk[i-1])!=can[k].zt)continue;
      if((can[j].zt&can[k].zt))continue;
      for(int l=1;l<=cnt;l++)//枚举这一行的状态
      {
        if((can[l].zt&can[i].zt))continue;
        if((can[l].zt&can[j].zt))continue;
        if((can[l].zt&zk[i])!=can[l].zt)continue;;
        dp[i][l][k]=max(dp[i][l][k],dp[i-1][k][j]+can[l].num);
        ans=max(ans,dp[i][l][k]);
      }
    }
  }
}
cout<<ans;
return 0;
}

by Violet___Evergarden @ 2021-09-20 10:18:58

样例没过

by Violet___Evergarden @ 2021-09-20 10:21:45

发现错误了，但60分


#include <iostream>
#include <climits>
using namespace std;
const int kMaxN=101;
const int kMaxM=11;
int dp[kMaxN][1<<10][1<<10];
int n,m;
int mp[kMaxN][kMaxM],ans;
int zk[kMaxN];
int cnt;
struct CAN
{
  int zt,num;
}can[1<<10];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
  zk[i]=0;
  for(int j=1;j<=m;j++)
  {
    char a;
    cin>>a;
    mp[i][j]=(a=='P'?1:0);
    zk[i]=(zk[i]<<1)+mp[i][j];
  }
}
for(int i=1;i<=(1<<m)-1;i++)
{
  if(i&(i<<1))continue;
  if(i&(i<<2))continue;
  if(i&(i>>1))continue;
  if(i&(1>>2))continue;
  can[++cnt].zt=i;
  int z=i;
  while(z)
  {
    if(z&1)
    {
      can[cnt].num++;
    }
    z>>=1;
  }
}
for(int i=1;i<=cnt;i++)
{
  if((can[i].zt&zk[1])!=can[i].zt)continue;
  dp[1][i][0]=can[cnt].num;
}
for(int i=1;i<=cnt;i++)
{
  if((can[i].zt&zk[1])!=can[i].zt)continue;
  for(int j=1;j<=cnt;j++)
  {
    if((can[j].zt&zk[2])!=can[j].zt)continue;
    if((can[i].zt&can[j].zt))continue;
    dp[2][j][i]=can[i].num+can[j].num;
  }
}
for(int i=3;i<=n;i++)
{
  for(int j=1;j<=cnt;j++)
  {
    if((can[j].zt&zk[i-2])!=can[j].zt)continue;
    for(int k=1;k<=cnt;k++)
    {
      if((can[k].zt&zk[i-1])!=can[k].zt)continue;
      if((can[j].zt&can[k].zt))continue;
      for(int l=1;l<=cnt;l++)
      {
        if((can[l].zt&can[k].zt))continue;
        if((can[l].zt&can[j].zt))continue;
        if((can[l].zt&zk[i])!=can[l].zt)continue;;
        dp[i][l][k]=max(dp[i][l][k],dp[i-1][k][j]+can[l].num);
        ans=max(ans,dp[i][l][k]);
      }
    }
  }
}
cout<<ans;
return 0;
}

by Violet___Evergarden @ 2021-09-20 10:25:38

改成这样90分


#include <iostream>
#include <climits>
using namespace std;
const int kMaxN=101;
const int kMaxM=11;
int dp[kMaxN][1<<8][1<<8];
int n,m;
int mp[kMaxN][kMaxM],ans;
int zk[kMaxN];
int cnt;
struct CAN
{
  int zt,num;
}can[1<<8];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
  zk[i]=0;
  for(int j=1;j<=m;j++)
  {
    char a;
    cin>>a;
    mp[i][j]=(a=='P'?1:0);
    zk[i]=(zk[i]<<1)+mp[i][j];
  }
}
for(int i=1;i<=(1<<m)-1;i++)
{
  if(i&(i<<1))continue;
  if(i&(i<<2))continue;
  if(i&(i>>1))continue;
  if(i&(1>>2))continue;
  can[++cnt].zt=i;
  int z=i;
  while(z)
  {
    if(z&1)
    {
      can[cnt].num++;
    }
    z>>=1;
  }
}
for(int i=1;i<=cnt;i++)
{
  if((can[i].zt&zk[1])!=can[i].zt)continue;
  dp[1][i][0]=can[cnt].num;
  ans=max(ans,dp[1][i][0]);
}
for(int i=1;i<=cnt;i++)
{
  if((can[i].zt&zk[1])!=can[i].zt)continue;
  for(int j=1;j<=cnt;j++)
  {
    if((can[j].zt&zk[2])!=can[j].zt)continue;
    if((can[i].zt&can[j].zt))continue;
    dp[2][j][i]=can[i].num+can[j].num;
    ans=max(ans,dp[2][j][i]);
  }
}
for(int i=3;i<=n;i++)
{
  for(int j=1;j<=cnt;j++)
  {
    if((can[j].zt&zk[i-2])!=can[j].zt)continue;
    for(int k=1;k<=cnt;k++)
    {
      if((can[k].zt&zk[i-1])!=can[k].zt)continue;
      if((can[j].zt&can[k].zt))continue;
      for(int l=1;l<=cnt;l++)
      {
        if((can[l].zt&can[k].zt))continue;
        if((can[l].zt&can[j].zt))continue;
        if((can[l].zt&zk[i])!=can[l].zt)continue;;
        dp[i][l][k]=max(dp[i][l][k],dp[i-1][k][j]+can[l].num);
        ans=max(ans,dp[i][l][k]);
      }
    }
  }
}
cout<<ans;
return 0;
}

by Violet___Evergarden @ 2021-09-20 10:33:18

下载了样例：

80 10
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
HHHHHHHHHH

输出：

216

by Violet___Evergarden @ 2021-09-20 10:35:20

AC了...

|