Dreamstar @ 2018-10-27 17:17:10
本题改成三维已A，但不明白二维做（f[i][j]为前i行第i行为状态j）为什么会WA，究竟漏了哪些状态？谢谢！ 附WA代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define rg register
#define maxn 200005
#define il inline
#define ll long long
#define mod 100000000
using namespace std;
il int read(){rg int x = 0 , w = 1;rg char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = (x<<3) + (x<<1) + ch - '0';ch = getchar();}return x * w;}
int n , m;
char s[maxn >> 3];
int flag[1005][1005] , st[1005] , num[1005];
int q[maxn];
ll dp[102][1100] , qq[102][1100] , need[1100];
ll max(ll a , ll b){
return (a > b) ? a : b;
}
ll solve(){
rg int maxstate = (1 << m) - 1;
for (rg int i = 1 ; i <= n ; ++i)
for (rg int j = 1 ; j <= m ; ++j){
st[i] = (st[i] << 1) + flag[i][j];
}
rg int cnt = 0 , cnt2 = 0;
for (rg int i = 0 ; i <= maxstate ; ++i)
if (!((i << 1) & i) && !((i << 2) & i))
q[++cnt] = i;
for (rg int i = 1 ; i <= n ; ++i){
for (rg int j = 1 ; j <= cnt ; ++j){
if ((q[j] & st[i]) == q[j])
qq[i][++num[i]] = j;
}
}
for (rg int i = 1 ; i <= cnt ; ++i){
rg int tmp = q[i];
while(tmp){
if (tmp & 1) ++need[i];
tmp >>= 1;
}
}
ll ans = 0;
for (rg int i = 1 ; i <= num[1] ; ++i){
dp[1][qq[1][i]] = need[qq[1][i]];
ans = max(dp[1][qq[1][i]] , ans);
}
for (rg int j = 1 ; j <= num[1] ; ++j)
for (rg int k = 1 ; k <= num[2] ; ++k)
if (!(q[qq[1][j]] & q[qq[2][k]])){
dp[2][qq[2][k]] = max(dp[1][qq[1][j]] + need[qq[2][k]] , dp[2][qq[2][k]]);
ans = max(dp[2][qq[2][k]] , ans);
}
for (rg int i = 3 ; i <= n ; ++i)
for (rg int j = 1 ; j <= num[i - 2] ; ++j)
for (rg int k = 1 ; k <= num[i - 1] ; ++k)
for (rg int l = 1 ; l <= num[i] ; ++l)
if (!(q[qq[i - 2][j]] & q[qq[i][l]]) && !(q[qq[i - 1][k]] & q[qq[i][l]]) && !(q[qq[i - 1][k]] & q[qq[i - 2][j]])){
dp[i][qq[i][l]] = max(dp[i][qq[i][l]] , dp[i - 2][qq[i - 2][j]] + need[qq[i][l]] + need[qq[i - 1][k]]) ;
ans = max(dp[i][qq[i][l]] , ans);
}
return ans;
}
int main(){
n = m = read();
for (rg int i = 1 ; i <= n ; ++i){
scanf("%s" , s);
for (rg int j = 1 ; j <= n ; ++j){
if (s[j - 1] == '.')
flag[i][j] = 1;
}
}
printf("%lld" , solve());
return 0;
}by 雷人 @ 2018-10-27 17:19:00
状压这东西就是玄学尤其是运算符优先级
by Dreamstar @ 2018-10-27 17:20:15
@雷人 谢谢回复，优先级没有问题，只是不知道二维为什么会漏状态...
by 雷人 @ 2018-10-27 17:25:36
@Dreamstar 它是影响两行的呀，所以需要开一维存上一行（Maybe吧状压太虚）
by Dreamstar @ 2018-10-27 17:29:19
@雷人 是的，但是我的方程是
dp[i][qq[i][l]] = max(dp[i][qq[i][l]] , dp[i - 2][qq[i - 2][j]] + need[qq[i][l]] + need[qq[i - 1][k]])我取i - 2行的MAX，再加上i - 1行和i行，因为所有状态都枚举了，所以感觉没错...请指点
by 雷人 @ 2018-10-27 17:56:09
@Dreamstar 你的预处理直接出锅了呀，num数组一堆1？？？重写一下试试，dp貌似没看出什么问题（可能是我水平太弱QAQ），但建议用三维更直观
by 雷人 @ 2018-10-27 17:58:04
@Dreamstar dp预处理很容易就出锅的
by Dreamstar @ 2018-10-27 19:39:09
@雷人 预处理没有锅的...我的AC代码只改动了维数及对应的转移方程，如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#define rg register
#define maxn 200005
#define il inline
#define ll long long
#define mod 100000000
using namespace std;
il int read(){rg int x = 0 , w = 1;rg char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = (x<<3) + (x<<1) + ch - '0';ch = getchar();}return x * w;}
int n , m;
char s[maxn >> 3];
int flag[1005][1005] , st[1005] , num[1005];
int q[10005];
int dp[101][70][70] , qq[102][1050] , need[1100];
ll max(ll a , ll b){
return (a > b) ? a : b;
}
ll solve(){
ll maxstate = (1 << m) - 1;
for (rg int i = 1 ; i <= n ; ++i)
for (rg int j = 1 ; j <= m ; ++j){
st[i] = (st[i] << 1) + flag[i][j];
}
rg int cnt = 0;
for (ll i = 0 ; i <= maxstate ; ++i)
if (!((i << 1) & i) && !((i << 2) & i))
q[++cnt] = i;
for (rg int i = 1 ; i <= n ; ++i){
for (rg int j = 1 ; j <= cnt ; ++j){
if ((q[j] & st[i]) == q[j])
qq[i][++num[i]] = j;
}
}
for (rg int i = 1 ; i <= cnt ; ++i){
rg int tmp = q[i];
while(tmp){
if (tmp & 1) ++need[i];
tmp >>= 1;
}
}
ll ans = 0;
for (rg int i = 1 ; i <= num[1] ; ++i)
ans = max(need[qq[1][i]] , ans);
for (rg int j = 1 ; j <= num[1] ; ++j)
for (rg int k = 1 ; k <= num[2] ; ++k)
if (!(q[qq[1][j]] & q[qq[2][k]])){
dp[2][qq[1][j]][qq[2][k]] = max(need[qq[1][j]] + need[qq[2][k]] , dp[2][qq[1][j]][qq[2][k]]);
ans = max(dp[2][qq[1][j]][qq[2][k]] , ans);
}
for (rg int i = 3 ; i <= n ; ++i)
for (rg int j = 1 ; j <= num[i - 2] ; ++j)
for (rg int k = 1 ; k <= num[i - 1] ; ++k)
if (!(q[qq[i - 1][k]] & q[qq[i - 2][j]]))
for (rg int l = 1 ; l <= num[i] ; ++l)
if (!(q[qq[i - 2][j]] & q[qq[i][l]]) && !(q[qq[i - 1][k]] & q[qq[i][l]])){
dp[i][qq[i - 1][k]][qq[i][l]] = max(dp[i][qq[i - 1][k]][qq[i][l]] , dp[i - 1][qq[i - 2][j]][qq[i - 1][k]] + need[qq[i][l]]) ;
ans = max(dp[i][qq[i - 1][k]][qq[i][l]] , ans);
}
return ans;
}
int main(){
n = read() , m = read();
for (rg int i = 1 ; i <= n ; ++i){
scanf("%s" , s);
for (rg int j = 1 ; j <= m ; ++j){
if (s[j - 1] == 'P')
flag[i][j] = 1;
}
}
printf("%lld" , solve());
return 0;
}不过我理解了一些了，是不是我只开一维就可能搞出一些本来不应存在的状态导致答案增加？谢谢！
by 雷人 @ 2018-10-27 20:09:29
@Dreamstar 差不多吧（蒟蒻瞎猜的）反正我觉得多开一维更稳，又不差这点空间
by Dreamstar @ 2018-10-30 21:18:13
@雷人 已找到错误，我枚举的是当前行状态与上两行状态匹配，上一行与上上行匹配，却漏掉了上一行与上上上行匹配，而要保证匹配就必须开三维，谢谢！
by 雷人 @ 2018-10-30 21:20:40
@Dreamstar 祝贺祝贺（吓我一跳