AcWing 271. 杨老师的照相排列

简介: AcWing 271. 杨老师的照相排列

271. 杨老师的照相排列 - AcWing题库

线性dp,

每一个ai < ni 并且 i = 1 或者 ai-1 > ai ; 这两个条件都必须满足;

初始化 f 00000 = 1 ,没有人安排的时候是一种情况

转移 如果a1 < n1 , 就让f[a1 + 1, a2 ,a3 ,a4, a5] += f[a1,a2,a3,a4,a5] ;


如果a2 < n2 并且 a1 > a2 ,则令f[a1 , a2+1 ,a3 , a4,a5] += f[a1,a2,a3,a4,a5] ;


以此类推

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std ;
typedef long long LL ;
const int N = 35 ;
LL f[N][N][N][N][N] ;// 一个五维数组,表示第i排已经安排了n个人;
int n ;
int m[6] ;//记录每一排的最多数量
int main(){
  while(cin >> n , n){
    memset(m,0,sizeof(m)) ;
    memset(f,0,sizeof(f)) ;
    for(int i = 1 ; i <= n; i ++) cin >> m[i] ;
    f[0][0][0][0][0] = 1 ;//初始化
    for(int a1 = 0 ; a1 <= m[1]  ; a1 ++){
      for(int a2 = 0 ; a2 <= m[2] && a2 <= a1 ; a2 ++){
        for(int a3 = 0 ; a3 <= m[3] && a3 <= a2; a3 ++){
          for(int a4 = 0 ; a4 <= m[4]&& a4 <= a3 ; a4 ++){
            for(int a5 = 0 ; a5 <= m[5] && a5 <= a4; a5 ++){
              LL &x =  f[a1][a2][a3][a4][a5] ;
              if(x == 0) continue ;
              if(a1 && a1 < m[1]) f[a1+1][a2][a3][a4][a5] += x ;
              if(a2 && a2 < m[2] && a1 > a2) f[a1][a2+1][a3][a4][a5] += x ;
              if(a3 && a3 < m[3] && a2 > a3) f[a1][a2][a3+1][a4][a5] += x ;
              if(a4 && a4 < m[4] && a3 > a4) f[a1][a2][a3][a4+1][a5] += x ;
              if(a5 && a5 < m[5] && a4 > a5) f[a1][a2][a3][a4][a5+1] += x ;
            }
          }
        }
      }
    }
    cout << f[m[1]][m[2]][m[3]][m[4]][m[5]] << endl ;
  }
  
}
目录
相关文章
AcWing 4261. 孤独的照片(每日一题)
AcWing 4261. 孤独的照片(每日一题)
【AcWing每日一题】4261. 孤独的照片
【AcWing每日一题】4261. 孤独的照片
73 0
【洛谷】独自一人听歌写题
【洛谷】独自一人听歌写题
74 0
|
存储
【蓝桥杯集训·每日一题】AcWing 3777. 砖块
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 递推
109 0
|
机器学习/深度学习
【蓝桥杯集训·每日一题】 AcWing 3996. 涂色
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 区间DP Unique函数
118 0
|
存储 算法 C++
【蓝桥杯集训·每日一题】AcWing 2058. 笨拙的手指
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 哈希表 秦九韶算法
165 0
|
存储 人工智能 算法
【蓝桥杯集训·最后一次周赛】AcWing 第 97 场周赛
文章目录 第一题 AcWing 4944. 热身计算 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第二题 AcWing 4945. 比大小 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第三题 AcWing 4946. 叶子节点 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解
132 0
|
JavaScript BI
【蓝桥杯集训·周赛】AcWing 第96场周赛
文章目录 第一题 AcWing 4876. 完美数 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第二题 AcWing 4877. 最大价值 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第三题 AcWing 4878. 维护数组 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解
86 0
|
存储 机器学习/深度学习 人工智能
【蓝桥杯集训·周赛】AcWing 第 95 场周赛
文章目录 第一题 AcWing 4873. 简单计算 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第二题 AcWing 4874. 约数 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第三题 AcWing 4875. 整数游戏 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解
112 0
|
存储 机器学习/深度学习 人工智能
【蓝桥杯集训·周赛】AcWing 第94场周赛
文章目录 第一题 AcWing 4870. 装物品 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第二题 AcWing 4871. 最早时刻 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 第三题 AcWing 4872. 最短路之和 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解
78 0