求助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 晴空一鹤 @ 2021-03-14 19:37:20

ooo 我再试一下

by zimujun @ 2021-03-14 19:37:27

@晴空一鹤 所以能不能先别交代码？现在这份代码通篇都是 bug，

而且请问您是否能看懂我说的话？我提到的问题您貌似一个都没改对

by zimujun @ 2021-03-14 19:38:50

那个数组开小现在好像没问题

by 晴空一鹤 @ 2021-03-14 19:40:50

2A2T6W

您继续说

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

@晴空一鹤 我在对着您的代码大改，您稍安勿躁，最多半小时

by 晴空一鹤 @ 2021-03-14 20:00:25

4A2T4W了

by zimujun @ 2021-03-14 20:03:41

@晴空一鹤

改完了，我给你加了注释，自己看看吧

#include<bits/stdc++.h>
using namespace std;
int s[101][171][171],cnt=0,ans=0;
int l[171];
int n,m;
char ccc;

int A[101];
//-----------------

/*快速读入*/
template <typename Temp> inline void read(Temp & res) {
    Temp fh = 1; res = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = -1;
    for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ '0');
    res = res * fh;
}
/*字符自动过滤，只取有关字符*/
inline void readch(char & ch) {
    ch = getchar(); while(!isalpha(ch)) ch = getchar();
}
//-------------------
void inline csh(int x)//给你减少了冗余计算，因为 (i >> 1) & (i >> 2) 和 i & (i >> 1) 等价。 
{
    for(int i=0;i<(1<<x);i++)
    if(((i&(i>>1))==0)&&((i&(i>>2))==0))
    l[++cnt]=i;
}
int inline cha(int y)//只用来计算贡献 
{
    int x=0;
    while(y)
    {
        x++;
        y -= (-y&y);
    }
    return x;
}
void inline dp()
{
    for(int i=1;i<=n;i++)
      for(int j=1;j<=cnt;j++)
      if(l[j] & A[i]) continue;//A[i] 是预处理出的地形数组，等价于您之前代码里的 aaa 数组，只不过预先处理成了二进制数，判断的时候只需要与上看看是不是为 0 就行了 
      else for(int x=1;x<=cnt;x++)
                if(l[x] & A[i - 1]) continue;//这三个 continue 都是为了直接减掉不合法转移 
                else
                for(int ll=1;ll<=cnt;ll++) {
                        if(i >= 2) if(l[ll] & A[i - 2]) continue;//这里还有个防止数组越界 
                        if((l[ll]&l[j]) == 0 && (l[j]&l[x]) == 0 && (l[ll] & l[j]) == 0) {
                            int v=cha(l[j]);
                            s[i][j][x]=max(s[i][j][x],s[i-1][x][ll]+v);
                            ans=max(ans,s[i][j][x]);
                                    }

                    }
}

void debug(int t) {
    for(int i = 1; i <= 10; ++i, t >>= 1) cout << (t & 1) << ' '; cout << '\n';
}

int main()
{
    read(n); read(m); csh(m);
    for(int i=1;i<=n;i++)
    {
      for(int j=0;j<m;++j) {
        readch(ccc);
        if(ccc == 'H') A[i] |= (1 << j);//自己看看怎么直接在输入的时候把 A 处理成二进制数 
            }
    }
    dp();
    printf("%d", ans);
    return 0;
} 

by zimujun @ 2021-03-14 20:04:22

上面的 debug 函数是我调试的时候用的，您可以不用管或者直接删了

by zimujun @ 2021-03-14 20:07:03

另外，尽量不要在代码中使用奇奇怪怪的变量名！

给一点让大家看的懂的变量名！

参考 hzwer 的博客

by 晴空一鹤 @ 2021-03-14 20:09:56

好的