首页 > 其他分享 >HDU4532(组合DP)

HDU4532(组合DP)

时间:2023-05-31 17:33:02浏览次数:116  
标签:组合 int LL 550 long DP include HDU4532 dp


题目:安排座位

 

解析:http://www.douban.com/note/269136472/

 

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
typedef long long LL;

const LL MOD=1000000007;

LL a[550];
LL A[550];
LL C[550][550];
LL dp[55][550];

void Init()
{
    for(int i=0; i<550; i++)
    {
        C[i][0]=C[i][i]=1;
        for(int j=1; j<i; j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
    }
    A[0]=1;
    for(int i=1; i<550; i++)
        A[i]=(A[i-1]*i)%MOD;
}

int main()
{
    Init();
    int T,n,tt=1;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1; i<=n; i++)
            cin>>a[i];
        memset(dp,0,sizeof(dp));
        dp[1][a[1]-1]=1;
        LL sum=a[1];
        for(int i=2; i<=n; i++)
        {
            for(int j=0; j<sum; j++)        //对每一种空位
                for(int k=1; k<=a[i]; k++)  //将a[i]个元素分成k组
                    for(int u=0; u<=j && u<=k; u++) //将u组放到前j个空位中
                        dp[i][j-u+a[i]-1-(k-1)]=(dp[i][j-u+a[i]-k]+(((dp[i-1][j]*C[j][u])%MOD*C[sum+1-j][k-u])%MOD*C[a[i]-1][k-1])%MOD)%MOD;
            sum+=a[i];
        }
        printf("Case %d: ",tt++);
        LL ans=dp[n][0];
        for(int i=1; i<=n; i++)    //对每一组,进行全排列
            ans=(ans*A[a[i]])%MOD;
        cout<<ans<<endl;
    }
    return 0;
}

 

标签:组合,int,LL,550,long,DP,include,HDU4532,dp
From: https://blog.51cto.com/u_16146153/6388680

相关文章

  • 玩转服务器之网站篇:新手使用WordPress搭建博客和静态网站部署
    静态网站部署和WordPress搭建博客都是网站运营中常见的工作。静态网站是一种不需要服务器端脚本的网站形式,通常使用HTML、CSS和JavaScript等静态资源进行构建和显示。而WordPress是一款流行的博客系统,可以帮助用户快速搭建博客网站。在之前的玩转服务器系列文章里,我们介绍了如何构......
  • 手机直播源码,android 轮播图(自定义组合控件)
    手机直播源码,android轮播图(自定义组合控件)1.项目gradle添加一下配置:  allprojects{ repositories{ ... maven{url'https://jitpack.io'} } } ​2.module中的gradle添加依赖:  dependencies{   implementation'com.github.truemi:SlideS......
  • 报错问题谷粒商城 Oss endpoint can‘t be empty
    报错信息:Causedby:java.lang.IllegalArgumentException:Ossendpointcan’tbeempty.网上查了一下说有两种可能第一种是springboot和springcloud版本不对应第二种错误说的是oss.yml格式错误 建议优先检查yml格式我的因为那天改配置的时候被家里猫按到了,然后没有发现,检......
  • dp模板
    dp类题目总结(双序列和背包问题):1、双序列题目最长回文子串最长公共子序列(diff实现)编辑距离交叉字符串特点:(1)单字符串dp,用二维dp,i,j表示s[i:j+1](2)双字符串的,dp[i][j]表示s1[:i]和s2[:j]推导s1[i]s2[j]关系2、背包类DP优先使用dfs+cache,逼不得已改dp3、博弈类dp,用dfs+cache......
  • Gym - 101170A[DP+思维]
    题目链接:https://vjudge.net/problem/Gym-101170A 解题思路:首先要确定的是,改变次数最多不会超过2*n次,因为n最多40,所以我们只要改变每个数的前两个最高位,肯定可以让n个数有序。然后我们就可以想办法搞个DP[i][j]表示将前i个数变成有序花了j次的最小值。为什么是最小值呢,维护最小......
  • Codeforces #564 (Div. 2) D. Nauuo and Circle[树形DP]
    题目链接:http://codeforces.com/contest/1173/problem/D 解题思路:首先得知道按照圆周顺序的话,那么一颗子树必须存放在连续的一段区间里面,现在我们假设根节点是1,那么一颗为u做根节点的子树他的方案数就是各个儿子的方案数的乘积最后再乘以儿子个数+1(u节点本身)的排列方案数。所......
  • 4543: [POI2014]Hotel加强版[树形DP+长链剖分]
    题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4543 解题思路:长链剖分定义:f[i][j]表示以i为根节点的子树,有多少个节点和i的距离是j的.g[i][j]表示以i为根节点的子树,在子树外一个距离i为j的点可以跟i子树内的两个点组成两两相等的方案数.那么就有:f[u][j+1]+=f[v......
  • 【视频】风险价值VaR原理与Python蒙特卡罗Monte Carlo模拟计算投资组合实例|附代码数
    原文链接:http://tecdat.cn/?p=22862 最近我们被客户要求撰写关于风险价值的研究报告,包括一些图形和统计输出。风险价值(VaR)是一种统计数据,用于量化公司、投资组合在特定时间范围内可能发生的财务损失程度什么是风险价值(VaR)?该指标最常被投资银行和商业银行用来确定其机构......
  • 插头DP 备忘
    插头DP备忘以前一直觉得没必要学,就是普通的状压,发现不学一下写起来有点难受的。最好的学习资料大概就是cdq的论文了。原文叫基于连通性状态压缩的动态规划问题。最常见的问题形式就是给个网格图,求某种回路或者类似的图形最优化或者计数。核心思想是把他转化为\(dp\),需要......
  • dp-runtime去Kafka依赖方案
    背景现有原生kafkaconnectruntime,在客户环境运行遇到诸多问题,问题列表如下:强依赖Kafka集群做任务分配、connector配置信息、connector状态管理、source进度维护等等当遇到数据量大、并行数多,topic数量较多时,可能引发kakfa集群的不稳定包括(节点宕机,controller切换等)从而引......