求助DP题

晴空一鹤 @ 2021-03-14 19:07:03

#include<bits/stdc++.h>
using namespace std;
int s[101][171][171],cnt=0,ans=0;
int l[171];
int n,m;
char aaa[101][101],ccc;
void inline csh(int x)
{
    for(int i=0;i<1<<x;i++)
    if(((i&(i>>1))==0)&&((i&(i>>2))==0)&&(((i>>1)&(i>>2))==0))
    l[++cnt]=i;
}
int inline cha(int y,int u)
{
    int x=0;
    while(y&(-y))
    {
        if(aaa[u][(int)log(y&(-y))+1]=='P')x++;
        y-=y&(-y);
    }
    return x;
}
void inline dp()
{
    for(int i=1;i<=n;i++)
      for(int j=1;j<=cnt;j++)
        for(int x=1;x<=cnt;x++)
           for(int ll=1;ll<=cnt;ll++)
           {
           int v=cha(l[j],i);
          if((l[ll]&l[j]&l[x])==0)
          s[i][l[j]][l[x]]=max(s[i][l[j]][l[x]],s[i-1][l[x]][l[ll]]+v);
          ans=max(ans,s[i][l[j]][l[x]]);
          }
}
int main()
{
    cin>>n>>m;ccc=getchar();
    for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=m;j++)
      cin>>aaa[i][j];
      ccc=getchar();
    }
    csh(m);
    dp();
    cout<<ans<<endl;
} 

by zimujun @ 2021-03-14 19:22:26

@晴空一鹤

状态预处理函数没有问题

但是您数组绝对开小了

因为您的 dp 数组中的第二三个下标调用的是 l_i ，但是 l_i 是有可能到 1024 的。

不过您这种问题也能解决。

by 晴空一鹤 @ 2021-03-14 19:22:42

@zimujunqwq

by zimujun @ 2021-03-14 19:23:05

@晴空一鹤

数组开小了跟 cnt 的大小无关

by 晴空一鹤 @ 2021-03-14 19:23:46

but 我并没有RE

by 晴空一鹤 @ 2021-03-14 19:25:52

@zimujunqwq

应该是跟cnt有关系

因为：

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

        for(int x=1;x<=cnt;x++)

           for(int ll=1;ll<=cnt;ll++)

by 晴空一鹤 @ 2021-03-14 19:27:39

ooo

我知道了

by 晴空一鹤 @ 2021-03-14 19:30:00

@zimujunqwq

可是我还是T+W了

by zimujun @ 2021-03-14 19:30:15

int main()
{
    csh(10); cout << l[60] << '\n';
    //dp();
    cout<<ans<<endl;
}

这是这份程序跑出来的结果：

585

然而您的代码中：

s[i][l[j]][l[x]]

int s[101][171][171];

您觉得呢

by zimujun @ 2021-03-14 19:35:41

@晴空一鹤

(l[ll]&l[j]&l[x])==0

这个是假的

反例（都是二进制下的）：

00100 00010 00100

分别对应十进制下的 4 2 4

显然，这三个二进制与起来为 0，但是转移是不合法的

by 晴空一鹤 @ 2021-03-14 19:36:05

但是改成

#include<bits/stdc++.h>
using namespace std;
int s[101][171][171],cnt=0,ans=0;
int l[171];
int n,m;
char aaa[101][101],ccc;
void inline csh(int x)
{
    for(int i=0;i<(1<<x);i++)
    if(((i&(i>>1))==0)&&((i&(i>>2))==0)&&(((i>>1)&(i>>2))==0))
    l[++cnt]=i;
}
int inline cha(int y,int u)
{
    int x=0;
    while(y&(-y))
    {
        if(aaa[u][(int)log(y&(-y))+1]=='P')x++;
        y-=y&(-y);
    }
    return x;
}
void inline dp()
{
    for(int i=1;i<=n;i++)
      for(int j=1;j<=cnt;j++)
        for(int x=1;x<=cnt;x++)
           for(int ll=1;ll<=cnt;ll++)
           {
           int v=cha(l[j],i);
          if((l[ll]&l[j]&l[x])==0)
          s[i][j][x]=max(s[i][j][x],s[i-1][x][ll]+v);
          ans=max(ans,s[i][j][x]);
          }
}
int main()
{
    cin>>n>>m;ccc=getchar();
    for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=m;j++)
      cin>>aaa[i][j];
      ccc=getchar();
    }
    csh(m);
    dp();
    cout<<ans<<endl;
} 

后仍旧T+W

您能帮我解释一下为什么会T吗？？（拜托大佬了）