AtCoder Grand Contest 030 (AGC030) F - Permutation and Minimum 动态规划
发布日期:2021-10-24 15:11:36 浏览次数:42 分类:技术文章

本文共 1699 字,大约阅读时间需要 5 分钟。

原文链接www.cnblogs.com/zhouzhendong/p/AGC030F.html

草率题解

对于每两个相邻位置,把他们拿出来。

如果这两个相邻位置都有确定的值,那么不管他。

然后把所有的这些数拿出来,分为两类,一类是没有被填入的,一类是被填入的。

然后大力DP即可。由于没有被填入的可以任意排列,所以最后还要乘上一个阶乘。

代码

#include 
#define clr(x) memset(x,0,sizeof x)#define For(i,a,b) for (int i=(a);i<=(b);i++)#define Fod(i,b,a) for (int i=(b);i>=(a);i--)#define fi first#define se second#define pb(x) push_back(x)#define mp(x,y) make_pair(x,y)#define outval(x) cerr<<#x" = "<
<
vi;LL read(){ LL x=0,f=0; char ch=getchar(); while (!isdigit(ch)) f|=ch=='-',ch=getchar(); while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return f?-x:x;}const int N=305*2,mod=1e9+7;int Pow(int x,int y){ int ans=1; for (;y;y>>=1,x=(LL)x*x%mod) if (y&1) ans=(LL)ans*x%mod; return ans;}void Add(int &x,int y){ if ((x+=y)>=mod) x-=mod;}void Del(int &x,int y){ if ((x-=y)<0) x+=mod;}int Add(int x){ return x>=mod?x-mod:x;}int Del(int x){ return x<0?x+mod:x;}int n;int a[N],b[N];int cnt=0,tot=0;int dp[N][N][N];vector
v;int main(){ n=read(); For(i,1,n*2){ a[i]=read(); if (a[i]!=-1) b[a[i]]=1; } For(i,1,n){ if (a[i*2-1]==-1&&a[i*2]==-1) cnt++,tot+=2; else if (a[i*2-1]==-1) tot+=2,v.pb(a[i*2]); else if (a[i*2]==-1) tot+=2,v.pb(a[i*2-1]); } For(i,1,n*2) if (!b[i]) v.pb(i); sort(v.begin(),v.end()); v.pb(0); reverse(v.begin(),v.end()); dp[0][0][0]=1; For(i,1,tot) For(j,0,tot) For(k,0,tot){ int val=dp[i-1][j][k]; if (!val) continue; if (!b[v[i]]){ Add(dp[i][j+1][k],val); if (j>0) Add(dp[i][j-1][k],val); if (k>0) Add(dp[i][j][k-1],(LL)val*k%mod); } else { Add(dp[i][j][k+1],val); if (j>0) Add(dp[i][j-1][k],val); } } int ans=dp[tot][0][0]; For(i,1,cnt) ans=(LL)ans*i%mod; cout<
<

转载于:https://www.cnblogs.com/zhouzhendong/p/AGC030F.html

转载地址:https://blog.csdn.net/weixin_30800807/article/details/94933531 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:[原创]通过IE8的测试来看CSS选择符的样式渲染优先级
下一篇:python实现邮件接口——smtplib模块

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.219.124.196]2024年03月03日 03时24分01秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

共享内存 java_java - Java客户端-服务器编程:客户端之间的共享内存 - 堆栈内存溢出... 2019-04-21
java布局管理器空布局_Java图形化界面设计——布局管理器之null布局(空布局)... 2019-04-21
java gas station_LeetCode – 774. Minimize Max Distance to Gas Station 2019-04-21
java项目无法加载到tomcat_eclipse+tomcat添加项目进来无法启动tomcat 2019-04-21
后缀树建立 java_实用算法实现-第 8 篇后缀树和后缀数组 [2 最长公共子串] 2019-04-21
java网络编程期末试题_java网络编程面试题【其中一小部分】 2019-04-21
estore java_estore2 - WEB源码|JSP源码/Java|源代码 - 源码中国 2019-04-21
java如何做表单校验_微信小程序实现表单校验功能 2019-04-21
matlab dwt2(),MATLAB小波变换指令及其功能介绍(超级有用) 2019-04-21
php sequelize,egg.js整合数据库ORM框架Sequelize 2019-04-21
php同时打开2个数据库,thinkphp3.2同时连接两个数据库的简单方法 2019-04-21
centos 开发php扩展,centos 安装php扩展redis 2019-04-21
php+跑buth,php 中函数获取可变参数的方法, 这个语法有点像 golang 语言中的 2019-04-21
cms 单点登录 php,Yii2 中实现单点登录的方法 2019-04-21
oracle自己运行,创建Oracle自动执行Job 2019-04-21
oracle报错00020,oracle启动 ORA-00020: maximum number of processes (%s) exceeded错误 2019-04-21
chmod 赋权所有_chmod 权限 命令详细用法 2019-04-21
html代码翻译_[译]您知道 HTML 的键盘标签吗? 2019-04-21
html抽奖代码_JavaScript高手之路:封装抽奖效果 2019-04-21
hadoop 3.3 一直停留在running wordcount_蛋价持续下跌,今日跌破3.3元大关!深秋季节价格还能反弹吗?... 2019-04-21