锐客网

  1. 首页 > it技术 > >

题解|【题解】洛谷P2051 中国象棋（状压dp）

30分做法
拿到这种题一开始肯定没有思路，而30分的数据比较小，所以我们可以暴力解决。dfs函数x代表行数，b[i]代表第i列有多少个炮了，我们知道如果某一列有两个炮，那那一行里的这一列一定不能再放炮了。分别循环表示一行里不放炮、放一个、放两个的情况，然后计算得到结果，可以解决30分。

#include #include #include #include #include using namespace std; const int mod=9999973; int n,m; int ans=0; int b[100]; void dfs(int x) { if(x==n+1) { ans++; return ; } dfs(x+1); for(int i=1; i<=m; i++) { if(b[i]<=1) { b[i]++; dfs(x+1); b[i]--; } } for(int i=1; i<=m; i++) { if(b[i]<=1) { b[i]++; for(int j=i+1; j<=m; j++) { if(b[j]<=1) { b[j]++; dfs(x+1); b[j]--; } } b[i]--; } } } int main() { scanf("%d%d",&n,&m); dfs(1); cout<

100分做法
对于正解的数据是比较大的，dfs肯定会TLE，所以满分做法是用状压dp解决。我们设一个f[i][j][k]数组代表当前为第几行，放1个炮的列数有i个，放两个炮的列数有j个。初始化f[0][0][0]为1。循环，并记录下不放、放1个和放2个时的列数，long long定义now=f[i][j][k]。不放炮时，直接过渡到下一行，得到f[i+1][r1][r2]=(f[i+1][r1][r2]+now)%mod。放一个炮时，可以在没有炮或有一个炮的那一列放，而这时炮的位置又有r0和r1种可能，所以要乘进去，得到状态转移方程。对于放两个炮则有在两个无炮列放，两个有一个炮列放和一个无一个有放，分别得到状态转移方程，注意这时要乘的可能性可能用到组合数，（在r0列中选两列）所以要写一个函数来计算组合数，最后将答案加起来即可，注意取mod。
#include #include #include #include #include #define ll long long using namespace std; const int maxn=110; const int mod=9999973; int f[maxn][maxn][maxn]; int n,m; int ans; int c(int x) { return (ll) x * (x-1) / 2 % mod; } int main() { scanf("%d%d",&n,&m); f[0][0][0]=1; for(int i=0; i=1) f[i+1][r1+1][r2]=(f[i+1][r1+1][r2]+now*r0%mod)%mod; if(r1>=1) f[i+1][r1-1][r2+1]=(f[i+1][r1-1][r2+1]+now*r1%mod)%mod; if(r0>=2) f[i+1][r1+2][r2]=(f[i+1][r1+2][r2]+now*c(r0)%mod)%mod; if(r1>=2) f[i+1][r1-2][r2+2]=(f[i+1][r1-2][r2+2]+now*c(r1)%mod)%mod; if(r0>=1&&r1>=1) f[i+1][r1][r2+1]=(f[i+1][r1][r2+1]+now*r0%mod*r1%mod)%mod; } for(int i=0; i<=m; i++) for(int j=0; i+j<=m; j++) ans+=f[n][i][j],ans%=mod; cout<

【题解|【题解】洛谷P2051 中国象棋（状压dp）】

    推荐阅读


    上一篇：感恩日记299/2018-6-9/31-99

    下一篇：vue img :src拼接问题