《算法竞赛进阶指南》0x51线性DP 照相馆排列
2021-04-08 19:28
标签:等价 using namespace cin ios win ++ names str 题目链接:https://www.acwing.com/problem/content/273/ 题目要求将N个人排成不超过五列,每列的人数限制而且递减,现在要求每行每列都是递减的方案的数量,通过状态集合以及转移规律,f[a][b][c][d][e]满足索引递减的性质 ,在转移的时候要维护这个性质,所以除了e以为的所有的索引-1情况都需要考虑,e-1的情况自然维护了这个性质。此外,从高到低排这些人,当前要排的人排在哪一行就是决策的划分过程,当前决策中的方案数量等价于之前阶段的某一个决策的方案数,所以直接累加转移的方案即可。 在DP问题中,集合和集合划分的概念十分重要,本问题中的集合上的属性是数量。 代码: 《算法竞赛进阶指南》0x51线性DP 照相馆排列 标签:等价 using namespace cin ios win ++ names str 原文地址:https://www.cnblogs.com/randy-lo/p/13377523.html#include