题解 [ARC132C] Almost Sorted
cjh20090318
·
·
题解
做这道题的时候注意到了同名题目 CF1730F Almost Sorted，没想到都是状压 DP。
题意
参见题意翻译。
分析
设 $f_{i,S}$ 表示前 $i$ 个数 $[i-d,i+d]$ 的占用情况（不包含已经确定的）为 $S$ 时的方案数。
如果第 $i$ 个数已经确定，那么直接从 $i-1$ 的状态进行转移。
否则就枚举每一个可能的位置，再从上一个进行转移即可。
因为不好描述具体实现就看代码吧，时间复杂度 $O(nd2^d)$。
## 代码
```cpp
//the code is from chenjh
#include<cstdio>
#include<cmath>
using namespace std;
const int mod=998244353;
int n,d,a[505],p[505];
int f[505][1<<11];
int main(){
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(~a[i]){
p[a[i]]=i;
if(abs(a[i]-i)>d) return puts("0"),0; //已经确定的不符合条件直接判无解。
}
}
**f=1;
for(int i=1,mS=1<<(d<<1|1);i<=n;i++)
if(p[i])for(int S=0;S<mS;++S){
bool fl=1;
for(int j=-d;j<=d;j++)if((i+j<1||i+j>n||~a[i+j])&&((S>>(j+d))&1)){fl=0;break;}//判断是否有被占用的不合法位置。
if(fl)
f[i][S]=(f[i-1][(S<<1)&(mS-1)]+f[i-1][(S<<1|1)&(mS-1)]);//从上一个状态转移，有两种情况。
}
else for(int S=0;S<mS;++S){
bool fl=1;
for(int j=-d;j<=d;j++)if((i+j<1||i+j>n||~a[i+j])&&((S>>(j+d))&1)){fl=0;break;}
if(fl)for(int j=-d;j<=d;j++)if((S>>(j+d))&1)
f[i][S]=(f[i][S]+(long long)f[i-1][((S^(1<<(j+d)))<<1)&(mS-1)]+f[i-1][((S^(1<<(j+d)))<<1|1)&(mS-1)])%mod;
}
int ans=0;
for(int S=0,mS=1<<(d<<1|1);S<mS;++S)ans=(ans+f[n][S])%mod;//将所有情况求和。
printf("%d\n",ans);
return 0;
}
```