ycyxh1 @ 2024-09-26 08:29:51
#include<bits/stdc++.h>
using namespace std;
int dp[2][1<<10+1][1<<10+1],n,m,val[1<<11],a[11],v[1<<11];
int js=0;
void dfs(int p,int w,int bj,int ww){
// printf("%d %d %d\n",p,w,bj);
if(p==m){
val[++js]=w;
v[js]=ww;
return;
}
if(bj==0){
dfs(p+1,w+(1<<p),2,ww+1);
dfs(p+1,w,0,ww);
}
else if(bj==1){
dfs(p+1,w,0,ww);
}
else if(bj==2){
dfs(p+1,w,1,ww);
}
}
signed main(){
scanf("%d%d",&n,&m);
dfs(0,0,0,0);
// for(int i=1;i<=js;i++){
// printf("%d %d\n",val[i],v[i]);
// }
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char b;
cin>>b;
if(b=='H'){
a[i]+=(1<<(j-1));
}
}
}
// for(int i=1;i<=n;i++){
// printf("%d ",a[i]);
// }
// printf("\n");
if(n==1){
int ans=0;
for(int i=1;i<=js;i++){
if((a[1]&val[i])==0){
ans=max(ans,v[i]);
}
}
printf("%d",ans);
return 0;
}
for(int i=1;i<=js;i++){
for(int j=1;j<=js;j++){
if(((val[i]&a[2])||(val[i]&val[j]))==0){
dp[1][val[i]][val[j]]=v[i]+v[j];
}
}
}
// for(int j=1;j<=js;j++){
// for(int k=1;k<=js;k++){
// printf("%d ",dp[1][val[j]][val[k]]);
// }
// }
// printf("\n");
for(int i=3;i<=n;i++){
for(int j=1;j<=js;j++){
for(int k=1;k<=js;k++){
dp[0][val[j]][val[k]]=dp[1][val[j]][val[k]];
dp[1][val[j]][val[k]]=-1001;
}
}
for(int j=1;j<=js;j++){
for(int k=1;k<=js;k++){
for(int p=1;p<=js;p++){
if(((val[p]&a[i])||(val[p]&val[j])||(val[p]&val[k]))==0){
dp[1][val[p]][val[k]]=max(dp[1][val[p]][val[k]],dp[0][val[k]][val[j]]+v[p]);
}
}
}
}
// for(int j=1;j<=js;j++){
// for(int k=1;k<=js;k++){
// printf("%d ",dp[1][val[j]][val[k]]);
// }
// }
// printf("\n");
}
int ans=0;
for(int i=1;i<=js;i++){
for(int j=1;j<=js;j++){
ans=max(ans,dp[1][val[i]][val[j]]);
}
}
printf("%d",ans);
return 0;
}by ycyxh1 @ 2024-09-26 09:24:44
20pts了QAQ
#include<bits/stdc++.h>
using namespace std;
int dp[2][1<<11+1][1<<11+1],n,m,val[1<<11],a[11],v[1<<11];
int js=0;
void dfs(int p,int w,int bj,int ww){
// printf("%d %d %d\n",p,w,bj);
if(p==m){
val[++js]=w;
v[js]=ww;
return;
}
if(bj==0){
dfs(p+1,w+(1<<p),2,ww+1);
dfs(p+1,w,0,ww);
}
else if(bj==1){
dfs(p+1,w,0,ww);
}
else if(bj==2){
dfs(p+1,w,1,ww);
}
}
signed main(){
scanf("%d%d",&n,&m);
dfs(0,0,0,0);
// for(int i=1;i<=js;i++){
// printf("%d %d\n",val[i],v[i]);
// }
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char b;
cin>>b;
if(b=='H'){
a[i]+=(1<<(j-1));
}
}
}
// for(int i=1;i<=n;i++){
// printf("%d ",a[i]);
// }
// printf("\n");
if(n==1){
int ans=0;
for(int i=1;i<=js;i++){
if((a[1]&val[i])==0){
ans=max(ans,v[i]);
}
}
printf("%d",ans);
return 0;
}
for(int i=1;i<=js;i++){
for(int j=1;j<=js;j++){
if(((val[i]&a[2])||(val[i]&val[j])||(val[j]&a[1]))==0){
dp[1][val[i]][val[j]]=v[i]+v[j];
}
}
}
// for(int j=1;j<=js;j++){
// for(int k=1;k<=js;k++){
// printf("%d ",dp[1][val[j]][val[k]]);
// }
// }
// printf("\n");
for(int i=3;i<=n;i++){
for(int j=1;j<=js;j++){
for(int k=1;k<=js;k++){
dp[0][val[j]][val[k]]=dp[1][val[j]][val[k]];
dp[1][val[j]][val[k]]=-1001;
}
}
for(int j=1;j<=js;j++){
for(int k=1;k<=js;k++){
for(int p=1;p<=js;p++){
if(((val[p]&a[i])||(val[p]&val[j])||(val[p]&val[k]))==0){
dp[1][val[p]][val[k]]=max(dp[1][val[p]][val[k]],dp[0][val[k]][val[j]]+v[p]);
}
}
}
}
// for(int j=1;j<=js;j++){
// for(int k=1;k<=js;k++){
// printf("%d ",dp[1][val[j]][val[k]]);
// }
// }
// printf("\n");
}
int ans=0;
for(int i=1;i<=js;i++){
for(int j=1;j<=js;j++){
ans=max(ans,dp[1][val[i]][val[j]]);
}
}
printf("%d",ans);
return 0;
}by ycyxh1 @ 2024-09-26 09:39:39
@ycyxh1
c,我是sb，a数组开小了
by crz_qwq @ 2024-09-26 12:42:16
捉