某dp题2
2024-08-24 15:06:47
P2401 不等数列
题目描述
将1到n任意排列,然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。问在所有排列中,有多少个排列恰好有k个“<”。答案对2015取模。
注:1n的排列指的是1n这n个数各出现且仅出现一次的数列。
输入输出格式
输入格式:
第一行2个整数n,k。
输出格式:
一个整数表示答案。
输入输出样例
输入样例#1:
5 2
输出样例#1:
66
说明
对于30%的数据:n <= 10
对于100%的数据:k < n <= 1000
这个是一个比较那啥的递推(dp)做法
具体就是考虑一个\(1-n\)自然数的排列
然后其中每两个相邻的数之间存在一定的大小关系
然后考虑下一个数:\(n+1\)
那么他比数列中所有的数都大
如果我们将这个\(n+1\)插入到数列中的某个位置
如果将其插入到产生<关系的两侧
那么产生的<关系的数量将不会改变
那么所有的<两端一共只有j+1个位置
同样
如果将n+1插入到一个>关系的两侧,会增加一个<关系
所有的>关系的两侧只有i-j个位置
那么根据这个关系来递推答案
设f[i][j]表示在\(1-i\)的所有排列中,有k个<关系的排列有多少个
那么递推式
\[f_{ij}=(j+1)\times f_{i-1 j}+(i-j)\times f_{i-1j-1}
\]
\]
所以
\[f(i,j) =
\begin{cases}
1 & \mbox{i=0, j=0} \\
(j+1)\times f(i-1,j)+(i-j)\times f(i-1,j-1)& \mbox{j<i}
\end{cases}
\]
\begin{cases}
1 & \mbox{i=0, j=0} \\
(j+1)\times f(i-1,j)+(i-j)\times f(i-1,j-1)& \mbox{j<i}
\end{cases}
\]
#include<iostream>
#include<cstdio>
#define N 15
using namespace std;
int f[N][N];
int n,k;
int main(){
cin>>n>>k;
for(int i=1;i<=n;++i)
f[i][0]=1;
for(int i=2;i<=n;++i)
for(int j=1;j<=min(i-1,k);++i)
f[i][j]=((j+1)*f[i-1][j]+(i-j)*f[i-1][j-1])%2015;
printf("%d",f[n][k]%2015);
return 0;
}
最新文章
- keycode
- linux 根据文件大小查找文件
- pay-as-you-go
- php进程的SIGBUS故障
- ExtJS笔记5 Components
- 音乐播放器 AVAudioPlayer、定时器、UISlider
- char和vchar
- grunt自动化工具
- 巧记--Css选择器
- Jade 报错
- OpenJDK1.8.0 源码解析————HashMap的实现(二)
- WCF扩展之实现ZeroMQ绑定和protocolBuffer消息编码(二)实现IRequestChannel(2016-03-15 12:35)
- mvc拦截器
- [转] Eclipse中已安装的插件如何卸载
- 【设计模式】原型模式 Pototype Pattern
- Http数据协商
- target与currentTarget与this的区别
- elasticsearch 使用快照进行备份
- 纯CSS3实现垂直居中的九种方法
- iOS: [UITableView reloadData]