NC556 题解 | #平衡的选择题#

题意分析

• 有n个多选题，每个多选题可以选择的情况有15种，$(A,B,C,D,AB,AC,AD,BC,BD,CD,ABC,ACD,ABD,BCD,ABCD)(A,B,C,D,AB,AC,AD,BC,BD,CD,ABC,ACD,ABD,BCD,ABCD)$(A,B,C,D,AB,AC,AD,BC,BD,CD,ABC,ACD,ABD,BCD,ABCD).现在，我们需要设计n个选择题的正确答案种，A和C选项数量差值不超过1，B和D选项数量差值不超过2.问有多少种情况。答案模1e9+7

思路分析

• 思路应该比较清晰，对动态规划熟练的话应该一眼就能看出这个需要用动态规划进行求解。我们首先来定义状态方程，我们定义一个三维的状态方程，$dp\left[i\right]\left[j\right]\left[k\right]dp[i][j][k]$dp[i][j][k]表示对于选完前$ii$i到题目之后，使A和C之间的数量差值不超过$jj$j和B和D之间的数量差值不超过$kk$k的选择的方案的数目。
• 但是我们如何表示这15种选择的方案呢？总不能一个一个用if进行判断吧，我们可以发现，这个选项的排列，其实和二进制有点关系。也就是这里有一个4位的二进制，A-D分别代表选项的从高到低的四位。如果对应位为1表示选择了这个选项。所以，我们可以从1到15进行枚举，numA=(i>>3)&1,numB=(i>>2)&1,numC=(i>>1)&1,numD=i&1

• 搞定了这个之后，我们再来看一个问题，A和C的数量不超过1，那么可能的情况就是A-C=-1,0,1,B和D的数量不超过2，B-D=-2,-1,0,1,2。我们为了用数组进行表示，对齐之后就是0,1,2和0，1，2，3，4.所以我们数组的空间大小就可以定义了。

解法一 动态规划

• 根据状态方程的定义，当前i状态的方案可以由i-1的状态的方案进行转移。所以就直接进行一个转移即可。
• 代码如下
  • 过程钟需要循环n次，然后每个需要枚举A和C以及B和D的差值，所以时间复杂度为$O\left(15n\right)O(15n)$O(15n),可以看作是$O\left(n\right)O(n)$O(n)
  • 定义的状态方程是$dp\left[1000010\right]\left[3\right]\left[5\right]dp[1000010][3][5]$dp[1000010][3][5],所以空间复杂度为$O\left(15n\right)O(15n)$O(15n),可以看作是$O\left(n\right)O(n)$O(n)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    typedef long long ll;
    const int mod=1e9+7;
    int dp[100010][3][5];
    int solve(int n) {
        // write code here
        // 计算初始的状态
        for(int i=1;i<=15;i++){
            int a=(i>>3)&1,b=(i>>2)&1,c=(i>>1)&1,d=i&1;
            dp[1][1-a+c][2+b-d]++;
        }
        
        // 每个状态i由i-1的状态转移过来
        for(int i=2;i<=n;i++){
        	// 枚举A和C的差值
            for(int j=0;j<3;j++){
            	// 枚举B和D的差值
                for(int k=0;k<5;k++){
                    for(int x=1;x<=15;x++){
                        int a=(x>>3)&1,b=(x>>2)&1,c=(x>>1)&1,d=x&1;
                        // 进行状态的转移
                        if(j+a-c>=0&&j+a-c<3&&k+b-d>=0&&k+b-d<5){
                            dp[i][j+a-c][k+b-d]=(dp[i][j+a-c][k+b-d]+dp[i-1][j][k])%mod;
                        }
                    }
                }
            }
        }
        
        int res=0;
        // 累加所有合法的情况
        for(int j=0;j<3;j++){
            for(int k=0;k<5;k++){
                res=(res+dp[n][j][k])%mod;
            }
        }
        
        
        return res;
    }
};

解法二 动态规划+滚动数组

• 我们观察上一种写法，我们发现每个状态i的转移只和状态i-1有关，所以其实可以利用滚动数组将其第一维优化为二维的。

• 滚动数组的大致原理如下，我们发现我们根本不会用到i-1之前的状态，那么就可以将其分为奇偶状态进行转移。

• 代码如下

  • 时间复杂度还是保持不变，过程钟需要循环n次，然后每个需要枚举A和C以及B和D的差值，所以时间复杂度为$O\left(15n\right)O(15n)$O(15n),可以看作是$O\left(n\right)O(n)$O(n)

  • 定义的状态方程是$dp\left[2\right]\left[3\right]\left[5\right]dp[2][3][5]$dp[2][3][5],所以空间复杂度为$O\left(30\right)O(30)$O(30),可以看作是$O\left(1\right)O(1)$O(1)

class Solution {
public:
   /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
    * @param n int整型 
    * @return int整型
    */
   typedef long long ll;
   const int mod=1e9+7;
   int dp[2][3][5];
   int solve(int n) {
       // write code here
       memset(dp,0,sizeof(dp));
       // 状态初始化操作
       for(int i=1;i<=15;i++){
           int a=(i>>3)&1,b=(i>>2)&1,c=(i>>1)&1,d=i&1;
           dp[1][1+a-c][2+b-d]++;
       }
       
       // 枚举每个位置的情况
       for(int i=2;i<=n;i++){
           // 由于只定义了两种状态，每种状态是由上一种状态转移过来的，所以需要先将当前这一种状态清零
           for(int j=0;j<3;j++){
               for(int k=0;k<5;k++){
                   dp[i&1][j][k]=0;
               }
           }
           for(int j=0;j<3;j++){
               for(int k=0;k<5;k++){
                   for(int x=1;x<=15;x++){
                       int a=(x>>3)&1,b=(x>>2)&1,c=(x>>1)&1,d=x&1;
                       // 每种状态由上一种状态转移过来
                       if(j+a-c>=0&&j+a-c<3&&k+b-d>=0&&k+b-d<5){
                           dp[i&1][j+a-c][k+b-d]=(dp[i&1][j+a-c][k+b-d]+dp[(i-1)&1][j][k])%mod;
                       }
                   }
               }
           }
       }
       
       int res=0;
       // 累加所有的情况
       for(int j=0;j<3;j++){
           for(int k=0;k<5;k++){
               res=(res+dp[n&1][j][k])%mod;
           }
       }
       
       
       return res;
   }
};