Bzoj3193:[JLOI2013]地形生成:dp+组合数学

题目链接：3193:[JLOI2013]地形生成

第一问：

每座山前面的山高度大于这座山的数量小于它的关键值，所以对于一座山，所有比他矮的山对他并没有什么影响

那就可以按照山的高度从高到矮排一发序，每座山只有他前面的山才会对他有影响

假设我们现在正在考虑第i座山，他前面有i-1座，它的关键值为k，则我们可以把他放到[1,min(k,i)]中的任意一个位置，组合数乘一下即可

但是会有山的高度相等的情况，我们假设[x,y]这一段的山高度都相等，x<i<=y，那么如果i前面与i高度相等的山的关键值大于i的关键值k，我们就没法计算i的可行位置了

所以在排序的时候加入第二关键字为关键值，从小到大排

这样排完序后，i的可行位置数量就可以确定为min(k,i)+i-x个，组合数乘一下即可

第二问：

使得等高线产生重复的还是高度相等的山，所以我们还得将一段高度相等的山同时考虑，设为[x,y]

设dp[i][j]为[x,y]中前i个山放在前j个位置的山的后面的方案数，两种方案不同当且仅当存在某一座山后面跟的山的数量不同

我们把[x,y]中的山一座一座地插进去，当前的山i可以插在每一座山后面，由于多了一座山所以不会产生重复

那么

我们发现

所以dp[i][j]=dp[i-1][j]+dp[i][j-1]；

列个表:

dp[1][j]=dp[0][j]+dp[1][j-1]；

dp[2][j]=dp[1][j]+dp[2[j-1]=dp[0][j]+dp[1][j-1]+dp[2][j-1]；

dp[3][j]=dp[2][j]+dp[3][j-1]=dp[0][j]+dp[1][j-1]+dp[2][j-1]+dp[3][j-1]；

……

dp[n][j]=dp[0][j]+dp[1][j-1]+dp[2][j-1]+……+dp[n][j-1]；

所以有

那个dp[0][j]显然为0

当然还可以都放在最开头即存在dp[i][0]这样的情况，且方案数为1

然后就可以前缀和优化一下做到了，最终复杂度为

因为区间大小和区间段数等问题实际复杂度很低

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
const int mod=2011;
struct Mountains{int h,rk;}m[maxn];
int n;
int dp[maxn],ans1=1,ans2=1;
bool cmp(const Mountains &a,const Mountains &b){
return a.h>b.h||(a.h==b.h&&a.rk<b.rk);
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;++i)
scanf("%d%d",&m[i].h,&m[i].rk),m[i].rk--;
sort(m+1,m+n+1,cmp);
for (int i=1;i<=n;++i){
int pos=i;
while (pos<=n&&m[pos].h==m[i].h) pos++; pos--;
memset(dp,0,sizeof(dp)); dp[0]=1;
for (int j=i;j<=pos;++j){
ans1=ans1*(min(i,m[j].rk+1)+j-i)%mod;
for (int k=1;k<=min(m[j].rk,i-1);++k) dp[k]=(dp[k-1]+dp[k])%mod;
}
int sum=0;
for (int j=0;j<=min(m[pos].rk,i-1);++j) sum=(sum+dp[j])%mod;
ans2=ans2*sum%mod;
i=pos;
}
printf("%d %dn",ans1,ans2);
}

最后

以上就是完美手链最近收集整理的关于Bzoj3193:[JLOI2013]地形生成:dp+组合数学的全部内容，更多相关Bzoj3193内容请搜索靠谱客的其他文章。