nuo0930 @ 2020-06-21 10:16:53
蒟蒻初学状压dp,样例都没有过
#include<iostream>
using namespace std;
int tot(int x) {
int ans=0;
while(x&1) {
ans++;
x>>=1;
}
return ans;
}
int dp[4][61][61];
int main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int s[61];
int t[61];
int n,m;
cin>>n>>m;
int cnt=0;
for(int i=0; i<1<<m; i++)
if(!(i&(i<<1))&&!(i&(i<<2))) {
s[++cnt]=i;
t[cnt]=tot(i);
}
int a[110]= {0};
char str[11];
for(int i=0; i<n; i++) {
cin>>str;
for(int j=m-1; j>=0; j--)
if(str[j]=='H')
a[i]|=(1<<i);
}
for(int i=1; i<=cnt; i++)
dp[1][i][1]=t[i];
for(int i=1; i<=cnt; i++)
for(int j=1; j<=cnt; j++)
dp[2][i][j]=max(dp[2][i][j],dp[1][j][1]+t[i]);
for(int i=3; i<=100; i++)
for(int j=1; j<=cnt; j++)
if(!(s[j]&a[i]))
for(int k=1; k<=cnt; k++)
if(!((s[k]&s[j])||(s[k]&a[i-1])))
for(int lk=1; lk<=cnt; lk++)
if(!((s[lk]&s[k])||(s[lk]&s[j])||(s[lk]&a[i-2])))
dp[i%3+1][j][k]=max(dp[i%3+1][j][k],dp[(i-1)%3+1][k][lk]+t[j]);
int ans=0;
for(int i=1; i<=cnt; i++)
for(int j=1; j<=cnt; j++)
ans=max(ans,dp[n%3+1][i][j]);
cout<<ans;
return 0;
}
by nuo0930 @ 2020-06-21 10:37:28
可是,还是错啊
by 一只书虫仔 @ 2020-06-21 10:42:53
% ClCN