bzoj 1151: [CTSC2007]动物园zoo

思路:因为每个人最多只能看到五个动物,我们考虑将其状压,f[ i ][ s ] 表示到了第 i 个位置, i, i + 1, i + 2, i + 3, i + 4这四个动物的状态为s,

此时的最大值。 因为它是一个环,所以我们考虑枚举前4位,这样就能dp啦,dp[i][s] = max(dp[i - 1][(15 & s) << 1], dp[i - 1][(15 & s) << 1 | 1]) + val[i][s];

val[ i ]][ s ] 是预处理出来,在i这个位置的人在s这个状态的贡献。

 #include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int,int>
#define piii pair<int, pair<int,int>> using namespace std; const int N=+;
const int M=1e4+;
const int inf=0x3f3f3f3f;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9 + ; int n, m, val[N][], dp[N][];
int main() {
scanf("%d%d", &n, &m);
for(int k = ; k <= m; k++) {
int pos; scanf("%d", &pos);
int cnt1, cnt2, s1 = , s2 = ;
scanf("%d%d", &cnt1, &cnt2);
for(int i = ; i <= cnt1; i++) {
int x; scanf("%d", &x);
s1 |= << ((x - pos + n) % n);
}
for(int i = ; i <= cnt2; i++) {
int x; scanf("%d", &x);
s2 |= << ((x - pos + n) % n);
} for(int j = ; j < ; j++) {
if(j & s1 || ( ^ j) & s2) {
val[pos][j]++;
}
}
} int ans = ;
for(int s1 = ; s1 < ; s1++) {
for(int i = ; i < ; i++) dp[][i] = -inf;
dp[][s1 << ] = ;
for(int i = ; i <= n; i++) {
for(int s = ; s < ; s++) {
dp[i][s] = max(dp[i - ][( & s) << ], dp[i - ][( & s) << | ]) + val[i][s];
}
}
ans = max(ans, max(dp[n][s1 << ], dp[n][s1 << | ]));
} printf("%d\n", ans);
return ;
}
/*
*/
上一篇:C语言 标准输入 清空缓存


下一篇:ARM与X86 CPU架构对比区别