rainbow_star @ 2021-10-20 09:26:00
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
ll n,m;
ll mapp[101];//(0是从左边开始的)压缩地图，mapp[i]压缩第i行,平原是 0,山丘是1
ll dp[5000][5000][3];
//滚动数组,dp[L][S]表示：上一行的状态是 L,当前状态是 S
ll summ[5000];//summ[i]状态i中有几个1
char c;
ll maxx;
ll answer;
ll getsum(ll x) //计算出所有状态下的summ
{
ll ans=0;
while(x!=0)
{
if(x&1==1)
ans++;
x>>=1;
}
return ans;
}
int main()
{
// freopen("pbzd.in","r",stdin);
ll i,j,k,l;
scanf("%lld%lld",&n,&m);
for(i=1;i<=n;i++)
{
getchar();
for(j=0;j<m;j++)
{
c=getchar();
if(c=='H')
mapp[i]+=1<<j;
}
}
maxx=(1<<m)-1;
for(i=0;i<=maxx;i++)
summ[i]=getsum(i);
for(i=1;i<=n;i++)//当前正在计算第几行的dp值
{
for(j=0;j<=maxx;j++)//枚举上一行状态
{
//判断是否放在了山丘上
if(j&mapp[i-1]!=0)
continue;
//判断每个状态有没有两个炮兵左右距离在两格之内
if(j&(j<<1)!=0||j&(j<<2)!=0||j&(j>>1)!=0||j&(j>>2)!=0)
continue;
for(k=0;k<=maxx;k++)//枚举这一行状态
{
//判断是否放在了山丘上
if(k&mapp[i]!=0)
continue;
//判断每个状态有没有两个炮兵左右距离在两格之内
if(k&(k<<1)!=0||k&(k<<2)!=0||k&(k>>1)!=0||k&(k>>2)!=0)
continue;
//判断每一列与上一行有没有炮兵在对应位置上
if(j&k!=0)
continue;
for(l=0;l<=maxx;l++)//枚举上上行的状态
{
//判断每一列与上上行有没有炮兵在对应位置上
if(k&l!=0||j&l!=0)
continue;
//判断是否放在了山丘上
if(l&mapp[i-2]!=0&&i!=1)
continue;
//判断每个状态有没有两个炮兵左右距离在两格之内
if(l&(l<<1)!=0||l&(l<<2)!=0||l&(l>>1)!=0||l&(l>>2)!=0)
continue;
dp[j][k][2]=max(dp[j][k][2],dp[l][j][1]+summ[k]);
// answer=max(dp[j][k][2],answer);
}
}
}
for(j=0;j<=maxx;j++)//枚举上一行状态
for(k=0;k<=maxx;k++)//枚举这一行状态
{
cout<<j<<" "<<k<<" "<<dp[j][k][2]<<endl;
dp[j][k][1]=dp[j][k][2];
dp[j][k][2]=summ[k];
}
}
for(j=0;j<=maxx;j++)//枚举上一行状态
for(k=0;k<=maxx;k++)//枚举这一行状态
answer=max(answer,dp[j][k][1]);
printf("%lld",answer);
return 0;
}by 白依尘_轩子墨 @ 2021-10-20 09:26:59
写丑了
#include<bits/stdc++.h>
using namespace std;
const int Maxn=1e6;
const int mod=1e9+7;
typedef long long ll;
namespace io{
const int _SIZE=(1<<21)+1;
char ibuf[_SIZE],*iS,*iT,c,stk[40];int tot;
#define gc()(iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,_SIZE,stdin),(iS==iT ?EOF:*iS++)):*iS++)
template<class I>
inline void read(I &_x){
I fl=1;
for(c=gc();c<'0'||c>'9';c=gc()) if(c=='-') fl=-1;
for(_x=0;c>='0'&&c<='9';c=gc()) _x=_x*10+(c&15);
_x*=fl;
}
template<class I>
inline void prt(I _x,char ch='\0'){
tot=0;
if(_x<0) putchar('-'),_x*=-1;
do{
stk[tot++]=_x%10|48;_x/=10;
}while(_x);
do{
putchar(stk[--tot]);
}while(tot);
if(ch)putchar(ch);
}
}
using io::read;
using io::prt;
ll ans;
ll num[Maxn],sta[Maxn],dp[105][200][200],F[Maxn];
ll n,m,cnt;
void init(){
sta[++cnt]=0;
for(int i=1;i<(1<<m);i++){
if((i&(i<<1))||(i&(i<<2))||(i&(i>>2))||(i&(i>>1))) continue;
sta[++cnt]=i;
for(int j=0;j<=m;j++)
if(i&(1<<j)) num[cnt]++;
}
return;
}
int main(){
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char ch;
cin>>ch;
F[i]=(F[i]<<1)+(ch=='H');
}
init();
for(int i=1;i<=cnt;i++){
if((sta[i]&F[1])) continue;
dp[1][i][0]=num[i];
}
for(int i=1;i<=cnt;i++){
if((sta[i]&F[2])) continue;
for(int j=1;j<=cnt;j++){
if((sta[i]&sta[j])||(sta[j]&F[1])) continue;
dp[2][i][j]=num[i]+num[j];
}
}
for(int i=3;i<=n;i++){
for(int j=1;j<=cnt;j++){
if(sta[j]&F[i]) continue;
for(int x=1;x<=cnt;x++){
if((sta[x]&F[i-1])||(sta[j]&sta[x])) continue;
for(int y=1;y<=cnt;y++){
if((sta[j]&sta[y])||(sta[x]&sta[y])||(sta[y]&F[i-2])) continue;
dp[i][j][x]=max(dp[i][j][x],dp[i-1][x][y]+num[j]);
}
}
}
}
for(int i=1;i<=cnt;i++)
for(int j=1;j<=cnt;j++)
ans=max(ans,dp[n][i][j]);
prt(ans);
return 0;
}这样写就过了
by 白依尘_轩子墨 @ 2021-10-20 09:34:16
小心位运算优先级
建议都加个括号
by FLAT_LCH @ 2021-10-20 09:37:28
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
by QAQQWQ @ 2021-10-20 09:38:48
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
by 白依尘_轩子墨 @ 2021-10-20 10:07:39
@QAQQWQ
by 白依尘_轩子墨 @ 2021-10-20 10:08:07
@QAQQWQ
by QAQQWQ @ 2021-10-20 10:12:53
@白依尘_轩子墨 扎不多的了
by 白依尘_轩子墨 @ 2021-10-20 10:24:41
@QAQQWQ
河南拔智齿
by K_srh @ 2021-11-13 14:44:13
保持队形