概述
题目链接: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
然后就可以前缀和优化一下做到了,最终复杂度为
因为区间大小和区间段数等问题实际复杂度很低
#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:[JLOI2013]地形生成:dp+组合数学所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复