求助，一晚上调到崩溃

shiroko2008 @ 2022-07-23 22:42:50

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
bool piece (int s,int k) {
    return s&(1<<k);
}
bool isok (int s) {
    for (int i=2;i<m;i++) if ((piece(s,i)&piece(s,i-1))||(piece(s,i)&piece(s,i-2))) return 0;
    return 1;
}
int count_bit (int s) {
    int ans=0;
    for (int i=0;i<m;i++) if (piece(s,i)) ans++;
    return ans;
}
int main()
{
    cin>>n>>m;
    char c[n][m];
    for (int i=0;i<n;i++) for (int j=0;j<m;j++) cin>>c[i][j];
    int s[100];
    memset(s,0,sizeof(s));
    for (int i=0;i<n;i++) for (int j=0;j<m;j++) if (c[i][j]=='P') s[i]|=(1<<j);
    int dp[2][1<<m][1<<m];
    memset(dp,0,sizeof(dp));
    for (int i=0;i<(1<<m);i++) {
        if (!isok(i)) continue;
        for (int j=0;j<(1<<m);j++) {
            if (!isok(j)) continue;
            if (i&j) continue;
            dp[0][i][j]=count_bit(i)+count_bit(j);
        }
    }
    for (int i=2;i<n;i++) {
        for (int x=s[i-2];x;x=(x-1)&s[i-2]) {
            if (!isok(x)) continue;
            //if (x&~s[i-2]) continue; 
            for (int y=(((1<<m)-1)-x)&s[i-1];y;y=(((1<<m)-1)-x)&s[i-1]&(y-1)) {
                if (!isok(y)) continue;
                //if (x&y) continue;
                //if (y&~s[i-1]) continue;
                //cout<<i<<' '<<((((1<<m)^x^y))&s[i])<<' '<<x<<' '<<y<<' '<<s[i]<<' '<<((1<<m-1))<<endl;
                for (int z=((((1<<m)-1)-x-y))&s[i];z;z=(z-1)&(((((1<<m)-1)-x-y))&s[i])) {
                    if (!isok(z)) continue;
                    //if (z&~s[i]) continue;
                    //if (x&z) continue;
                    //if (y&z) continue;
                    dp[1][y][z]=count_bit(z)+dp[0][x][y];
                    //cout<<i<<' '<<x<<' '<<y<<' '<<z<<' '<<endl;
                }
            }
        }
        for (int x=0;x<(1<<m);x++) for (int y=0;y<(1<<m);y++) dp[0][x][y]=dp[1][x][y];
    }
    int ans=0;
    for (int x=0;x<(1<<m);x++) for (int y=0;y<(1<<m);y++) ans=max(ans,dp[0][x][y]);
    cout<<ans<<endl;
    //cout<<isok(24)<<' '<<piece(145,3)<<' '<<(6&~s[0])<<' '<<((1<<m)&~s[0])<<' '<<s[2];
    //cout<<s[2];
    return 0;
}

by shiroko2008 @ 2022-07-24 09:36:59

已A，此贴终

by 阴语飞 @ 2022-09-03 19:18:13

@lzber 求助 俺也一样咋办

by shiroko2008 @ 2022-09-03 20:48:09

@阴语飞

原代码有两处问题：

1. 状态转移时没有更新最优解
2. 没有考虑一行都没有炮兵的情况，正解应在循环体的最后特判，跳出循环 附AC代码：

   
   #include<iostream>
   #include<algorithm>
   #include<cstring>
   using namespace std;
   int n,m;
   bool piece (int s,int k) {
   return s&(1<<k);
   }
   bool isok (int s) {
   for (int i=2;i<m;i++) if ((piece(s,i)&piece(s,i-1))||(piece(s,i)&piece(s,i-2))) return 0;
   if (piece(s,0)&piece(s,1)) return 0;
   return 1;
   }
   int count_bit (int s) {
   int ans=0;
   for (int i=0;i<m;i++) if (piece(s,i)) ans++;
   return ans;
   }
   int main()
   {
   cin>>n>>m;
   char c[n][m];
   for (int i=0;i<n;i++) for (int j=0;j<m;j++) cin>>c[i][j];
   int s[100];
   memset(s,0,sizeof(s));
   for (int i=0;i<n;i++) for (int j=0;j<m;j++) if (c[i][j]=='P') s[i]|=(1<<j);
   int dp[2][1<<m][1<<m];
   memset(dp,0,sizeof(dp));
   for (int i=0;i<(1<<m);i++) {
       if (!isok(i)) continue;
       for (int j=0;j<(1<<m);j++) {
           if (!isok(j)) continue;
           if (i&j) continue;
           dp[0][i][j]=count_bit(i)+count_bit(j);
       }
   }
   for (int i=2;i<n;i++) {
       for (int x=s[i-2];;x=(x-1)&s[i-2]) {
           if (!isok(x)) continue;
           //if (x&~s[i-2]) continue; 
           for (int y=(((1<<m)-1)^x)&s[i-1];;y=(((1<<m)-1)^x)&s[i-1]&(y-1)) {
               if (!isok(y)) continue;
               //if (x&y) continue;
               //if (y&~s[i-1]) continue;
               //cout<<i<<' '<<((((1<<m)^x^y))&s[i])<<' '<<x<<' '<<y<<' '<<s[i]<<' '<<((1<<m-1))<<endl;
               for (int z=((((1<<m)-1)^x^y))&s[i];;z=(z-1)&(((((1<<m)-1)^x^y))&s[i])) {
                   if (!isok(z)) continue;
                   //if (z&~s[i]) continue;
                   //if (x&z) continue;
                   //if (y&z) continue;
                   dp[1][y][z]=max(dp[1][y][z],count_bit(z)+dp[0][x][y]);
                   //cout<<i<<' '<<x<<' '<<y<<' '<<z<<' '<<endl;
                   if (z==0) break;
               }
               if (y==0) break;
           }
           if (x==0) break;
       }
       for (int x=0;x<(1<<m);x++) for (int y=0;y<(1<<m);y++) dp[0][x][y]=dp[1][x][y];
   }
   int ans=0;
   for (int x=0;x<(1<<m);x++) for (int y=0;y<(1<<m);y++) ans=max(ans,dp[0][x][y]);
   cout<<ans<<endl;
   //cout<<isok(24)<<' '<<piece(145,3)<<' '<<(6&~s[0])<<' '<<((1<<m)&~s[0])<<' '<<s[2];
   //cout<<s[2];
   return 0;
   }
   ``

by shiroko2008 @ 2022-09-03 20:50:09

@阴语飞 缩进挂了，这是代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
bool piece (int s,int k) {
    return s&(1<<k);
}
bool isok (int s) {
    for (int i=2;i<m;i++) if ((piece(s,i)&piece(s,i-1))||(piece(s,i)&piece(s,i-2))) return 0;
    if (piece(s,0)&piece(s,1)) return 0;
    return 1;
}
int count_bit (int s) {
    int ans=0;
    for (int i=0;i<m;i++) if (piece(s,i)) ans++;
    return ans;
}
int main()
{
    cin>>n>>m;
    char c[n][m];
    for (int i=0;i<n;i++) for (int j=0;j<m;j++) cin>>c[i][j];
    int s[100];
    memset(s,0,sizeof(s));
    for (int i=0;i<n;i++) for (int j=0;j<m;j++) if (c[i][j]=='P') s[i]|=(1<<j);
    int dp[2][1<<m][1<<m];
    memset(dp,0,sizeof(dp));
    for (int i=0;i<(1<<m);i++) {
        if (!isok(i)) continue;
        for (int j=0;j<(1<<m);j++) {
            if (!isok(j)) continue;
            if (i&j) continue;
            dp[0][i][j]=count_bit(i)+count_bit(j);
        }
    }
    for (int i=2;i<n;i++) {
        for (int x=s[i-2];;x=(x-1)&s[i-2]) {
            if (!isok(x)) continue;
            //if (x&~s[i-2]) continue; 
            for (int y=(((1<<m)-1)^x)&s[i-1];;y=(((1<<m)-1)^x)&s[i-1]&(y-1)) {
                if (!isok(y)) continue;
                //if (x&y) continue;
                //if (y&~s[i-1]) continue;
                //cout<<i<<' '<<((((1<<m)^x^y))&s[i])<<' '<<x<<' '<<y<<' '<<s[i]<<' '<<((1<<m-1))<<endl;
                for (int z=((((1<<m)-1)^x^y))&s[i];;z=(z-1)&(((((1<<m)-1)^x^y))&s[i])) {
                    if (!isok(z)) continue;
                    //if (z&~s[i]) continue;
                    //if (x&z) continue;
                    //if (y&z) continue;
                    dp[1][y][z]=max(dp[1][y][z],count_bit(z)+dp[0][x][y]);
                    //cout<<i<<' '<<x<<' '<<y<<' '<<z<<' '<<endl;
                    if (z==0) break;
                }
                if (y==0) break;
            }
            if (x==0) break;
        }
        for (int x=0;x<(1<<m);x++) for (int y=0;y<(1<<m);y++) dp[0][x][y]=dp[1][x][y];
    }
    int ans=0;
    for (int x=0;x<(1<<m);x++) for (int y=0;y<(1<<m);y++) ans=max(ans,dp[0][x][y]);
    cout<<ans<<endl;
    //cout<<isok(24)<<' '<<piece(145,3)<<' '<<(6&~s[0])<<' '<<((1<<m)&~s[0])<<' '<<s[2];
    //cout<<s[2];
    return 0;
}

by 阴语飞 @ 2022-09-03 21:16:36

@lzber okok谢谢