SSerWarriоrs_Cat @ 2020-08-20 10:50:30
RT，调了 0.5h 硬是什么都没看出来……
过了样例，WA 10pts
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
char s[20];
int n, m, len, ok[80], num[80], f[110][80][80], a[110], ans;
inline int num1(int x){
int ans = 0;
while(x){
++ans;
x &= x - 1;
}
return ans;
}
int main(){
//freopen("P2704.in", "r", stdin);
//freopen("P2704.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i){
scanf("%s", s);
for(int j = 0; j < m; ++j){
a[i] = (a[i] << 1) + (s[j] == 'P');
}
}
for(int i = 0; i < (1 << m); ++i)
if(!(i & (i << 1)) && !(i & (i << 2)) && !(i & (i >> 1)) && !(i & (i >> 2)))
ok[++len] = i, num[len] = num1(i);
for(int i = 1; i <= len; ++i)
if(ok[i] | a[1] == a[1])
f[1][i][0] = num[i];
for(int i = 1; i <= len; ++i)
for(int j = 1; j <= len; ++j)
if((ok[i] | a[2] == a[2]) && (ok[j] | a[1] == a[1]) && !(ok[i] & ok[j]))
f[2][i][j] = num[i] + num[j];
for(int i = 3; i <= n; ++i)
for(int j = 1; j <= len; ++j)
if(ok[j] | a[i] == a[i])
for(int k = 1; k <= len; ++k)
if((ok[k] | a[i - 1] == a[i - 1]) && !(ok[j] & ok[k]))
for(int l = 1; l <= len; ++l)
if((ok[l] | a[i - 2] == a[i - 2]) && !(ok[k] & ok[l]) && !(ok[j] & ok[l]))
f[i][j][k] = max(f[i][j][k], f[i - 1][k][l] + num[j]);
for(int i = 1; i <= len; ++i) for(int j = 1; j <= len; ++j) ans = max(ans, f[n][i][j]);
printf("%d", ans);
return 0;
}
如果是一些申必错误请 D 死这个彩笔。
by SSerWarriоrs_Cat @ 2020-08-20 10:53:55
草，代码放讨论版咋这么丑。
好看一点的
by SSerWarriоrs_Cat @ 2020-08-20 10:55:37
@Reaper 除了第一个点全 WA
by STL_Lover @ 2020-08-20 11:01:52
@Warriоrs_Cat 找到错误了。
| 的优先级较低，所以某些地方要加括号。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
char s[20];
int n, m, len, ok[80], num[80], f[110][80][80], a[110], ans;
inline int num1(int x){
int ans = 0;
while(x){
++ans;
x &= x - 1;
}
return ans;
}
int main(){
//freopen("P2704.in", "r", stdin);
//freopen("P2704.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i){
scanf("%s", s);
for(int j = 0; j < m; ++j){
a[i] = (a[i] << 1) + (s[j] == 'P');
}
}
for(int i = 0; i < (1 << m); ++i)
if(!(i & (i << 1)) && !(i & (i << 2)) && !(i & (i >> 1)) && !(i & (i >> 2)))
ok[++len] = i, num[len] = num1(i);
for(int i = 1; i <= len; ++i)
if((ok[i] | a[1]) == a[1])
f[1][i][0] = num[i];
for(int i = 1; i <= len; ++i)
for(int j = 1; j <= len; ++j)
if(((ok[i] | a[2]) == a[2]) && ((ok[j] | a[1]) == a[1]) && !(ok[i] & ok[j]))
f[2][i][j] = num[i] + num[j];
for(int i = 3; i <= n; ++i)
for(int j = 1; j <= len; ++j)
if((ok[j] | a[i]) == a[i])
for(int k = 1; k <= len; ++k)
if((ok[k] | a[i - 1]) == a[i - 1] && !(ok[j] & ok[k]))
for(int l = 1; l <= len; ++l)
if((ok[l] | a[i - 2]) == a[i - 2] && !(ok[k] & ok[l]) && !(ok[j] & ok[l]))
f[i][j][k] = max(f[i][j][k], f[i - 1][k][l] + num[j]);
for(int i = 1; i <= len; ++i) for(int j = 1; j <= len; ++j) ans = max(ans, f[n][i][j]);
printf("%d", ans);
return 0;
}by SSerWarriоrs_Cat @ 2020-08-20 11:03:48
@STL_Lover A 了，感谢/qq
by STL_Lover @ 2020-08-20 11:04:35
@Warriоrs_Cat 用位运算的时候一定要注意加括号啊qaq
by SSerWarriоrs_Cat @ 2020-08-20 11:04:41
不过位运算优先级咋还比 == 低啊/fad/fad/fad
zblzblzbl
by STL_Lover @ 2020-08-20 11:06:53
@Warriоrs_Cat 建议看看这里
by __Watcher @ 2020-08-20 11:16:48
orz orz orz %%%