样例输出5求调

CNS_5t0_0r2 @ 2024-07-06 11:32:13

#include<iostream>
#include<cstring>
using namespace std;
const int N = 109,M = 10,K = 109;
int n,m;
char c[N][M];
int valid_stat[K],count[K]/*第i个合法状态中1的个数*/,cnt;
int valid[N][K];//valid[i][j]：状态j在第i行是否合法
int dp[N][K][K];//dp[i][j][k]：第i行状态为j，第i - 1行状态为k的最多可摆放数量
int lowbit(int x){
    return x & (-x);
}
int popcount(int x){
    int ret = 0;
    for(;x;x -= lowbit(x))
        ret++;
    return ret;
}
bool check(int x){//状态x之间1的间隔是否不小于2
    while(lowbit(x) < x){
        int lb = lowbit(x);
        x -= lb;
        if(lowbit(x) / lb < 8)
            return false;
    }
    return true;
}
bool check2(int row,int x){
    for(int k = 0;k < m;k++)
        if(((x >> k) & 1) && c[row][k] == 'H')//在山地设置炮兵阵地，不合法
            return false;
    return true;
}
int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        cin >> c[i];
    int tot = 1 << m;//状态总量

    for(int i = 0;i < tot;i++)
        if(check(i)){
            cnt++;
            valid_stat[cnt] = i;
            count[cnt] = popcount(i);
        }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= cnt;j++){
            int stat = valid_stat[j];
            valid[i][j] = check2(i,stat);
        }
    }
    memset(dp,128,sizeof dp);
    dp[0][1][1] = 0;

    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= cnt;j++){
            int stat1 = valid_stat[j];//第i行状态
            if(!valid[i][j])
                continue;
            for(int k = 1;k <= cnt;k++){
                int stat2 = valid_stat[k];//第i - 1行状态
                if(!valid[i - 1][k])
                    continue;
                if(stat1 & stat2)
                    continue;
                int Max = 0;
                for(int l = 1;l <= cnt;l++){
                    int stat3 = valid_stat[l];
                    if(stat1 & stat3)
                        continue;
                    Max = max(Max,dp[i - 1][k][l]);
                }
                dp[i][j][k] = Max + count[j];
            }
        }
    }
    int ans = 0;
    for(int j = 1;j <= cnt;j++){
        int stat1 = valid_stat[j];//第i行状态
        if(!valid[n][j])
            continue;
        for(int k = 1;k <= cnt;k++){
            int stat2 = valid_stat[k];//第i - 1行状态
            if(!valid[n - 1][k])
                continue;
            if(stat1 & stat2)
                continue;
            ans = max(ans,dp[n][j][k]);
        }
    }
    cout << ans;
    return 0;
}

by HakureiReimu_cjrljpx @ 2024-07-06 21:51:11

一开始预处理时，第一行要特殊处理一下，代码如下（打注释的代码是调试用的不用管）：

#include<iostream>
#include<cstring>
using namespace std;
const int N = 109,M = 10,K = 109;
int n,m;
char c[N][M];
int valid_stat[K],count[K]/*第i个合法状态中1的个数*/,cnt;
int valid[N][K];//valid[i][j]：状态j在第i行是否合法
int dp[N][K][K];//dp[i][j][k]：第i行状态为j，第i - 1行状态为k的最多可摆放数量
int lowbit(int x){
    return x & (-x);
}
int popcount(int x){
    int ret = 0;
    for(;x;x -= lowbit(x))
        ret++;
    return ret;
}
bool check(int x){//状态x之间1的间隔是否不小于2
    while(lowbit(x) < x){
        int lb = lowbit(x);
        x -= lb;
        if(lowbit(x) / lb < 8)
            return false;
    }
    return true;
}
bool check2(int row,int x){
    for(int k = 0;k < m;k++)
        if(((x >> k) & 1) && c[row][k] == 'H')//在山地设置炮兵阵地，不合法
            return false;
    return true;
}
/*
void f(int x){
    for(int c=0;c<m;++c){
        printf("%d",x&1);
        x>>=1;
    }
    putchar(' ');
}*/
int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        cin >> c[i];
    int tot = 1 << m;//状态总量

    for(int i = 0;i < tot;i++)
        if(check(i)){
            cnt++;
            valid_stat[cnt] = i;
            count[cnt] = popcount(i);
        }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= cnt;j++){
            int stat = valid_stat[j];
            valid[i][j] = check2(i,stat);
        }
    }
    memset(dp,128,sizeof dp);
    dp[0][1][1] = 0;
    /*改动的地方*/
    //第一行特别处理
    for(int j = 1;j <= cnt;j++){
        int stat1 = valid_stat[j];
        if(!valid[1][j])
            continue;
        for(int k = 1;k <= cnt;k++){
            dp[1][j][k] = count[j];
            //f(valid_stat[j]),f(valid_stat[k]);
            //printf(" %d %d\n",1,dp[1][j][k]);
        }
    }

    for(int i = 2;i <= n;i++){
        for(int j = 1;j <= cnt;j++){
            int stat1 = valid_stat[j];//第i行状态
            if(!valid[i][j])
                continue;
            for(int k = 1;k <= cnt;k++){
                int stat2 = valid_stat[k];//第i - 1行状态
                if(!valid[i - 1][k])
                    continue;
                if(stat1 & stat2)
                    continue;
                int Max = 0;
                for(int l = 1;l <= cnt;l++){
                    int stat3 = valid_stat[l];
                    if(stat1 & stat3)
                        continue;
                    Max = max(Max,dp[i - 1][k][l]);
                }
                dp[i][j][k] = Max + count[j];
                //f(valid_stat[j]),f(valid_stat[k]);
                //printf(" %d %d\n",i,dp[i][j][k]);
            }
        }
    }
    int ans = 0;
    for(int j = 1;j <= cnt;j++){
        int stat1 = valid_stat[j];//第i行状态
        if(!valid[n][j])
            continue;
        for(int k = 1;k <= cnt;k++){
            int stat2 = valid_stat[k];//第i - 1行状态
            if(!valid[n - 1][k])
                continue;
            if(stat1 & stat2)
                continue;
            //printf("%d %d\n",ans,dp[n][j][k]);
            ans = max(ans,dp[n][j][k]);
        }
    }
    cout << ans;
    return 0;
}

改代码不能通过全部测试点https://www.luogu.com.cn/record/164338531

by HakureiReimu_cjrljpx @ 2024-07-06 22:02:25

现在能过了。

最后用dp数组更新ans时没必要特判，因为dp的时候已经特判了。如果特判的话当n=1时，由于第一排前面没有两排，但特判会特判和前面两排有没有冲突，会出现问题。

把特判删掉即可AC：

#include<iostream>
#include<cstring>
using namespace std;
const int N = 109,M = 10,K = 109;
int n,m;
char c[N][M];
int valid_stat[K],count[K]/*第i个合法状态中1的个数*/,cnt;
int valid[N][K];//valid[i][j]：状态j在第i行是否合法
int dp[N][K][K];//dp[i][j][k]：第i行状态为j，第i - 1行状态为k的最多可摆放数量
int lowbit(int x){
    return x & (-x);
}
int popcount(int x){
    int ret = 0;
    for(;x;x -= lowbit(x))
        ret++;
    return ret;
}
bool check(int x){//状态x之间1的间隔是否不小于2
    while(lowbit(x) < x){
        int lb = lowbit(x);
        x -= lb;
        if(lowbit(x) / lb < 8)
            return false;
    }
    return true;
}
bool check2(int row,int x){
    for(int k = 0;k < m;k++)
        if(((x >> k) & 1) && c[row][k] == 'H')//在山地设置炮兵阵地，不合法
            return false;
    return true;
}
/*
void f(int x){
    for(int c=0;c<m;++c){
        printf("%d",x&1);
        x>>=1;
    }
    putchar(' ');
}*/
int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        cin >> c[i];
    int tot = 1 << m;//状态总量

    for(int i = 0;i < tot;i++)
        if(check(i)){
            cnt++;
            valid_stat[cnt] = i;
            count[cnt] = popcount(i);
        }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= cnt;j++){
            int stat = valid_stat[j];
            valid[i][j] = check2(i,stat);
        }
    }
    memset(dp,128,sizeof dp);
    dp[0][1][1] = 0;
    /*改动的地方*/
    //第一行特别处理
    for(int j = 1;j <= cnt;j++){
        int stat1 = valid_stat[j];
        if(!valid[1][j])
            continue;
        for(int k = 1;k <= cnt;k++){
            dp[1][j][k] = count[j];
            //f(valid_stat[j]),f(valid_stat[k]);
            //printf(" %d %d\n",1,dp[1][j][k]);
        }
    }

    for(int i = 2;i <= n;i++){
        for(int j = 1;j <= cnt;j++){
            int stat1 = valid_stat[j];//第i行状态
            if(!valid[i][j])
                continue;
            for(int k = 1;k <= cnt;k++){
                int stat2 = valid_stat[k];//第i - 1行状态
                if(!valid[i - 1][k])
                    continue;
                if(stat1 & stat2)
                    continue;
                int Max = 0;
                for(int l = 1;l <= cnt;l++){
                    int stat3 = valid_stat[l];
                    if(stat1 & stat3)
                        continue;
                    Max = max(Max,dp[i - 1][k][l]);
                }
                dp[i][j][k] = Max + count[j];
                //f(valid_stat[j]),f(valid_stat[k]);
                //printf(" %d %d\n",i,dp[i][j][k]);
            }
        }
    }
    int ans = 0;
    for(int j = 1;j <= cnt;j++){
        for(int k = 1;k <= cnt;k++){
            //printf("%d %d\n",ans,dp[n][j][k]);
            ans = max(ans,dp[n][j][k]);
        }
    }
    cout << ans;
    return 0;
}

by CNS_5t0_0r2 @ 2024-07-07 09:36:39

@HakureiReimu_cjrljpx thx