O2导致RE?
查看原帖
O2导致RE?
24695
Wh_Xcjm楼主2021/5/1 21:27

求教原因: 未吸氧AC:https://www.luogu.com.cn/record/50168719 吸氧RE:https://www.luogu.com.cn/record/50169191 从自定义函数中挪到主程序AC:https://www.luogu.com.cn/record/50169230 附吸氧RE程序:

// dp化改写:
#include <queue>
#include <stdio.h>
#include <string.h>

using namespace std;
#define qr read()
inline int read() {
    int x = 0;
    scanf("%d", &x);
    return x;
}
const int maxN = 1e5 + 5;
const int maxM = 21;
const int maxQ = (1 << 20) + 200;

int N = qr, M = qr;
int a[maxN];
int f[maxQ];
int qz[maxN][maxM];
int sum[maxQ];
int ans[maxQ];

int* siz = qz[N];

inline int count(int x) {
    int summ = 0;
    for(int i = 0; i < M; i++) {
        if(x & 1 << i) { summ += siz[i]; }
    }
    return summ;
}
int dpp() {
    ans[0] = 0;
    for(int statu = 1; statu < 1 << M; statu++)
        for(int i = 0; i < M; i++) {
            if((statu & 1 << i) == 0) continue;
            int nxsta  = statu ^ 1 << i;
            int qzl    = qz[sum[nxsta]][i];
            int qzr    = qz[sum[statu]][i];
            ans[statu] = min(~ans[statu] ? ans[statu] : N, ans[nxsta] + siz[i] - (qzr - qzl));
        }
}
int main() {
    memset(ans, -1, sizeof ans);
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j < M; j++) { qz[i][j] = qz[i - 1][j]; }
        a[i] = qr - 1;
        qz[i][a[i]]++;
    }
    for(int i = 0; i < 1 << M; i++) { sum[i] = count(i); }
    dpp();
    printf("%d\n", ans[(1 << M) - 1]);
    return 0;
}

挪到主程序即

... ...

int main() {
    memset(ans, -1, sizeof ans);
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j < M; j++) { qz[i][j] = qz[i - 1][j]; }
        a[i] = qr - 1;
        qz[i][a[i]]++;
    }
    for(int i = 0; i < 1 << M; i++) { sum[i] = count(i); }
    ans[0] = 0;
    for(int statu = 1; statu < 1 << M; statu++)
        for(int i = 0; i < M; i++) {
            if((statu & 1 << i) == 0) continue;
            int nxsta  = statu ^ 1 << i;
            int qzl    = qz[sum[nxsta]][i];
            int qzr    = qz[sum[statu]][i];
            ans[statu] = min(~ans[statu] ? ans[statu] : N, ans[nxsta] + siz[i] - (qzr - qzl));
        }
    printf("%d\n", ans[(1 << M) - 1]);
    return 0;
}
2021/5/1 21:27
加载中...