求教原因: 未吸氧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;
}