《算法竞赛进阶指南》0x51线性DP 照相馆排列

2021-04-08 19:28

阅读：444

标签：等价 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问题中，集合和集合划分的概念十分重要，本问题中的集合上的属性是数量。

代码：

#include
#include
#includestring.h>
using namespace std;
const int maxn = 31;
typedef long long ll;
ll f[maxn][maxn][maxn][maxn][maxn];
int n;
int main(){
    while(scanf("%d",&n) && n){
        int s[5]={0};
        for(int i=0;i>s[i];
        memset(f,0,sizeof(f));
        f[0][0][0][0][0]=1;
        for(int a=0;a0];a++)//保证后一排填的人比前面的小 
            for(int b=0;b1],a);b++)
                for(int c=0;c2],b);c++)
                    for(int d=0;d3]);d++)
                        for(int e=0;e4],d);e++)
                        {// f[a][b][c][d][e]满足索引递减的性质 
                            ll& v=f[a][b][c][d][e];
                            if(a && a>b)v+=f[a-1][b][c][d][e];
                            if(b && b>c)v+=f[a][b-1][c][d][e];
                            if(c && c>d)v+=f[a][b][c-1][d][e];
                            if(d && d>e)v+=f[a][b][c][d-1][e];
                            if(e)v+=f[a][b][c][d][e-1];
                        }
        
        printf("%lld\n",f[s[0]][s[1]][s[2]][s[3]][s[4]]);
    }
}

《算法竞赛进阶指南》0x51线性DP 照相馆排列

标签：等价 using namespace cin ios win ++ names str

原文地址：https://www.cnblogs.com/randy-lo/p/13377523.html

上一篇：JAVA——重点非阻塞模型：NIO模型及IO操作步骤

下一篇：删除列Table.RemoveColumns（Power Query 之 M 语言）

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：《算法竞赛进阶指南》0x51线性DP 照相馆排列
文章链接：http://soscw.com/index.php/essay/73008.html

亲，登录后才可以留言！

《算法竞赛进阶指南》0x51线性DP 照相馆排列

评论

热门文章

推荐文章

最新文章

置顶文章