洛谷 P2051 [AHOI2009]中国象棋状态压缩思想DP-白红宇

洛谷 P2051 [AHOI2009]中国象棋状态压缩思想DP

阅读量：5137 次

发布时间：2019-06-13

本文共 2681 字，大约阅读时间需要 8 分钟。

题意：

　　给定一个n*m的空棋盘，问合法放置任意多个炮有多少种情况。合法放置的意思是棋子炮不会相互打到。

思路：

　　这道题我们可以发现因为炮是隔一个棋子可以打出去，所以每一行每一列最多放置两个炮。

　　这样子我们就可以试着压缩状态，记录前i行有几列是放一个棋子的，有几列是放两个棋子的，有几列是不放棋子的。

　　即设dp[ i ][ j ] [ k ] 表示前 i 行，有 j 列是放一个棋子的，有k列是放两个棋子的，有 m - j - k列是不放棋子的。

　　又由于每行最多可以放两个棋子，所以可以退出第i行和第i-1行的关系。

#include 
     
      #include  
      
       #include  
       
        #include   
        
         #include   
         
          #include   
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    #include 
                     
                      #include 
                      
                       using namespace std;#define lson (l , mid , rt << 1)#define rson (mid + 1 , r , rt << 1 | 1)#define debug(x) cerr << #x << " = " << x << "\n";#define pb push_back#define pq priority_queuetypedef long long ll;typedef unsigned long long ull;//typedef __int128 bll;typedef pair
                       
                         pll;typedef pair
                        
                          pii;typedef pair
                         
                           p3;//priority_queue
                          
                            q;//这是一个大根堆q//priority_queue
                           
                            
                             ,greater
                             
                               >q;//这是一个小根堆q#define fi first#define se second//#define endl '\n'#define OKC ios::sync_with_stdio(false);cin.tie(0)#define FT(A,B,C) for(int A=B;A <= C;++A) //用来压行#define REP(i , j , k) for(int i = j ; i < k ; ++i)#define max3(a,b,c) max(max(a,b), c);#define min3(a,b,c) min(min(a,b), c);//priority_queue

, greater

>que;const ll mos = 0x7FFFFFFF; //2147483647const ll nmos = 0x80000000; //-2147483648const int inf = 0x3f3f3f3f;const ll inff = 0x3f3f3f3f3f3f3f3f; //18const int mod = 9999973;const double esp = 1e-8;const double PI=acos(-1.0);const double PHI=0.61803399; //黄金分割点const double tPHI=0.38196601;template

inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x;}/*-----------------------showtime----------------------*/ const int maxn = 200; ll dp[maxn][maxn][maxn]; ll c[maxn][maxn]; int n,m; void init(){ c[0][0] = 1; for(int i=1; i<=m; i++){ for(int j=0; j<=i; j++){ if(j==0) c[i][j] = 1; else if(j==i) c[i][j] = 1; else c[i][j] = (c[i-1][j] + c[i-1][j-1])%mod; } } }int main(){ scanf("%d%d", &n, &m); init(); dp[0][0][0] = 1; for(int i=1; i<=n; i++){ for(int j=0; j<=m; j++){ for(int k=0; k<=m-j; k++){ ll tmp = dp[i-1][j][k]; if(k>0) tmp = tmp + c[j+1][1] * dp[i-1][j+1][k-1] % mod; if(k>1) tmp = tmp + c[j+2][2] * dp[i-1][j+2][k-2] % mod; if(j>0) tmp = tmp + c[m-k-j+1][1] * dp[i-1][j-1][k] % mod; if(j>1) tmp = tmp + c[m-k-j+2][2] * dp[i-1][j-2][k] % mod; if(k>0) tmp = tmp + c[j][1] * c[m-j-k+1][1] * dp[i-1][j][k-1]%mod; tmp = tmp % mod; dp[i][j][k] = tmp % mod; } } } ll ans = 0; for(int j=0; j<=m; j++){ for(int k=0; k<=m-j; k++){ ans = (ans + dp[n][j][k]) % mod; } } printf("%lld\n", ans); return 0;}

转载于:https://www.cnblogs.com/ckxkexing/p/10288296.html

你可能感兴趣的文章