_l_l_l_l_l_ @ 2021-12-19 11:17:18
1 1
P答案:1
可以hack第2、4篇题解
by _l_l_l_l_l_ @ 2021-12-19 11:17:31
@小粉兔
by 小粉兔 @ 2021-12-19 15:19:22
@WenZKbb 能解释一下为啥能 hack 吗
by _l_l_l_l_l_ @ 2021-12-19 21:17:01
@小粉兔
只有一块平原,显然是最多放1个炮兵部队
不过把第2和4篇的代码放到ide里运行发现输出的是0
所以可以hack
by 小粉兔 @ 2021-12-19 23:42:23
@WenZKbb 他们错的原因是什么
by _l_l_l_l_l_ @ 2021-12-20 20:14:40
@小粉兔
这是我的AC代码，对于这组数据也是正确的
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
//状压DP 这就像摆国王 不过攻击范围大了些 最开始要构造前两行
int n,m,sit[1001],use[1001],cnt=0,terrain[1001],ans=-1e9;//sit[i]--第i种摆法用二进制数的表示 use[i]--sit[i]用了几个人
//terrain[i]--二进制表示第i行的地形(山是1 地是0),好用&判断大炮是不是跑山上去了
int f[205][205][101];//f[pre][now][i]--第i行按now摆 上一行是pre 可以放几个兵 摆法的二进制存在一个数组里,而不做下标,不然内存爆炸
char ch;
int count_one(int x)//找1的个数
{
int tot=0;
while(x>0)//类似拆位
{
if((x&1))
++tot;
x=x>>1;
}
return tot;
}
//这题坑了我一整天
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>ch;//scanf会读\n
if(ch=='H')
terrain[i]=(terrain[i]<<1)+1;//后面加一个山地
else
{
terrain[i]=(terrain[i]<<1)+0;//后面加一个平原
}
}
}
const int N=(1<<m);//二进制数表示的摆法最大是几 注意1行是m个
for(int i=0;i<N/*最大其实是到N-1*/;i++)//看哪些sit可以
{
if((i&(i<<1))||(i&(i<<2)))continue;//炮之间的距离必须>1
sit[++cnt]=i;
use[cnt]=count_one(i);
if(!(sit[cnt]&terrain[1]))//ERROR
{
f[0][cnt][1]=max(use[cnt],f[0][cnt][1]);//ERROR
}
ans=max(ans,f[0][cnt][1]);//ERROR
}
//单独做第二行
if(n>=2)//ERROR
{
for(int i=1;i<=cnt;i++)//第1行地形
for(int j=1;j<=cnt;j++)//第二行地形
{
if((sit[j]&sit[i])||(sit[j]&terrain[2])||(sit[i]&terrain[1]))continue;
f[i][j][2]=max(f[i][j][2],use[i]+use[j]);
ans=max(f[i][j][2],ans);//ERROR
}
}
for(int i=3;i<=n;i++)//枚举行
for(int j=1;j<=cnt;j++)//枚举这行摆法
{
if((sit[j]&terrain[i]))continue;//提前判断能加快速度
for(int k=1;k<=cnt;k++)//上一行摆法
{
if((sit[j]&sit[k])||(sit[k]&terrain[i-1]))continue;
for(int l=1;l<=cnt;l++)//上上一行摆法
{
if((sit[j]&sit[l])||(sit[k]&sit[l]))/*会误伤*/continue;
if((sit[j]&terrain[i])||(sit[k]&terrain[i-1])||(sit[l]&terrain[i-2]))/*山*/continue;
f[k][j][i]=max(f[k][j][i],f[l][k][i-1]+use[j]);
ans=max(ans,f[k][j][i]);
}
}
}
printf("%d\n",ans);
return 0;
}这是第二篇题解(https://www.luogu.com.cn/blog/xcgzyouxiao/solution-p2704)
#include<iostream>
using namespace std;
int n,m,ans,dp[(1<<10)][(1<<10)][3]/*滚动数组*/,a[105],Sum[(1<<10)];
char x;
int getsum(int S) //当前状态 S 里面包含几个 1
{
int tot=0;
while(S) {if(S&1) tot++; S>>=1;}
return tot;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>x,a[i]<<=1,a[i]+=(x=='H'?1:0); //转成二进制数
for(int i=0;i<(1<<m);i++)
Sum[i]=getsum(i); //初始化 Sum 数组
for(int S=0;S<(1<<m);S++)
if(!(S&a[0] || (S&(S<<1)) || (S&(S<<2))))
dp[0][S][0]=Sum[S]; //初始化
for(int L=0;L<(1<<m);L++)
for(int S=0;S<(1<<m);S++)
if(!(L&S || L&a[0] || S&a[1] || (L&(L<<1)) || (L&(L<<2)) || (S&(S<<1)) || (S&(S<<2)))) //谜之一长串特判
dp[L][S][1]=Sum[S]+Sum[L];
for(int i=2;i<n;i++)
for(int L=0;L<(1<<m);L++)
{
if(L&a[i-1] || (L&(L<<1)) || (L&(L<<2))) continue; //特判
for(int S=0;S<(1<<m);S++)
{
if(S&a[i] || L&S || (S&(S<<1)) || (S&(S<<2))) continue;
for(int FL=0;FL<(1<<m);FL++)
{
if(FL&L || FL&S || FL&a[i-2] || (FL&(FL<<1)) || (FL&(FL<<2))) continue;
dp[L][S][i%3]=max(dp[L][S][i%3],dp[FL][L][(i-1)%3]+Sum[S]); //滚动数组的实现方法
}
}
}
for(int L=0;L<(1<<m);L++)
for(int S=0;S<(1<<m);S++)
ans=max(ans,dp[L][S][(n-1)%3]); //结束状态可以是最后一行的任何状态
cout<<ans;
return 0;
}请看他的代码第22~25行
for(int L=0;L<(1<<m);L++)
for(int S=0;S<(1<<m);S++)
if(!(L&S || L&a[0] || S&a[1] || (L&(L<<1)) || (L&(L<<2)) || (S&(S<<1)) || (S&(S<<2)))) //谜之一长串特判
dp[L][S][1]=Sum[S]+Sum[L];
这是在单独计算第二行(因为一个炮兵能攻击到他的前面两行，所以需要手动求出第1和2行才能开始递推),然而他没有判断第二行是否存在,所以遇到只有1行的数据就出错了
看第4篇题解(https://www.luogu.com.cn/blog/henryhe/solution-p2704)
他的代码
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,k;
int s[1005],g[1005];
int f[102][1005][1005],ans;
char ma[103];
int map[103];
int get(int x)//计算某一状态含有多少个1(即有多少个炮兵)
{
int e=0;
while(x>0)
{
++e;
x-=x&(-x);
}
return e;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)//读入地图，将山地（不能放兵）的地方设为1
{
scanf("%s",ma);
for(int j=0;j<m;++j)
if(ma[j]=='H') map[i]+=1<<j;
}
for(int i=0;i<=(1<<m)-1;++i)//枚举所有的状态
if(((i&(i<<1))==0)&&((i&(i<<2))==0)&&((i&(i>>1))==0)&&((i&(i>>2))==0))//判断每个1左右各两个是否有1，即判断这种状态是否存在
{
++k;
s[k]=i;
g[k]=get(i);
if((i&map[1])==0) f[1][0][k]=g[k];//初始化第一行
}
//初始化第二行
for(int i=1;i<=k;++i)//枚举第一行状态
for(int j=1;j<=k;++j)//枚举第二行状态
if(((s[i]&s[j])==0)&&((s[j]&map[2])==0)) f[2][i][j]=max(f[2][i][j],f[1][0][i]+g[j]);//判断是否与地形和第一行冲突
//dp过程
for(int i=3;i<=n;++i)//枚举当前行数
for(int j=1;j<=k;++j)//枚举当前行数状态
if((map[i]&s[j])==0)//不与地形冲突
for(int p=1;p<=k;++p)//枚举前一行状态
if((s[p]&s[j])==0)//当前行状态不与前一行冲突
for(int q=1;q<=k;++q)//枚举前两行
//不与前两行冲突，且前两行自身不冲突
if(((s[q]&s[p])==0)&&((s[q]&s[j])==0)) f[i][p][j]=max(f[i][p][j],f[i-1][q][p]+g[j]);
for(int i=1;i<=k;++i)//枚举最后两行为结尾的情况，统计答案
for(int j=1;j<=k;++j)
ans=max(f[n][i][j],ans);
cout<<ans; //输出
return 0;
}
请看第37~39行
for(int i=1;i<=k;++i)//枚举第一行状态
for(int j=1;j<=k;++j)//枚举第二行状态
if(((s[i]&s[j])==0)&&((s[j]&map[2])==0)) f[2][i][j]=max(f[2][i][j],f[1][0][i]+g[j]);//判断是否与地形和第一行冲突
他与第二篇犯了同一个错误，没判断第二行是否存在就开始计算第二行
by 小粉兔 @ 2021-12-20 20:23:11
@WenZKbb 感谢您的贡献
by 红黑树 @ 2022-03-02 14:33:07
小粉兔楼下！
by Coros_Trusds @ 2022-03-31 19:33:25
@小粉兔 您能改改第二篇题解的代码吗，我联系不上作者。。对于第二篇题解，将代码初始化改为
for(int i=1;i<=cnt;i++){ //处理第一排
if((start[i]&F[1])==0){ //不能与地形冲突
f[1][i][1]=gs[i];
}
}
就能过了
by AThls123 @ 2022-11-11 11:48:40
小粉兔楼下！