[JLOI2013]地形生成

题目

好一道语文题

首先你得先排序一下，就是高度为第一关键字从大到小，权值为第而关键字从小到大

第一问看上去非常简单，我们考虑每次把一座山插入到已有的排列中去，这样我们能用乘法原理合并答案，如果没有高度相同的，每个山的贡献就是\(min(a[i],v,i)\)，如果有高度相同的，我们就一次处理完所有高度相同的

总之还是比较简单的

第二问变得有点困难，看起来好像不是很好解决了

还是每次都把高度相同的一起加入

我们考虑把这个问题转化成最经典的球盒模型，大致能搞成这个样子

把\(n\)个没有标号的球放进\(m\)个盒子里，允许有盒子为空，但是第\(i\)个球只能放到 前\(p_i\)个盒子里

我们把\(p_i\)从小到大排序后，可以强行规定\(p_i\)小的只能出现在\(p_i\)大的球之前，这样就变成了无标号的了

于是就有一个暴力\(dp\)，设\(dp[i][j]\)表示第\(i\)个球严格放在第\(j\)个盒子里的方案数

于是有

\[dp[i][j]=\sum_{i=1}^jdp[i-1][k]\]

显然可以前缀和优化

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define min std::min
inline int read() {
    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int mod=2011;
const int maxn=1e3+5;
struct Mt {int h,v;} a[maxn];
inline int cmp(Mt A,Mt B) {
    if(A.h==B.h) return A.v<B.v;
    return A.h>B.h;
}
int n,ans1,ans2;
int dp[maxn][maxn],pre[maxn][maxn];
inline int calc(int l,int r,int m) {
    for(re int i=1; i<=min(m,a[l].v); i++) dp[l][i]=1;
    for(re int i=1; i<=m; i++) pre[l][i]=pre[l][i-1]+dp[l][i];
    for(re int i=l+1; i<=r; i++) {
        for(re int j=1; j<=min(a[i].v,m); j++) dp[i][j]=pre[i-1][j];
        for(re int j=1; j<=m; j++) pre[i][j]=(pre[i][j-1]+dp[i][j])%mod;
    }
    return pre[r][m];
}
int main() {
    n=read();
    for(re int i=1; i<=n; i++) a[i].h=read(),a[i].v=read();
    std::sort(a+1,a+n+1,cmp);
    ans1=1,ans2=1;int l=1;
    for(re int i=1; i<=n; i++)
        if(a[i].h!=a[i+1].h) {
            ans2=calc(l,i,l)*ans2%mod;
            for(re int j=l; j<=i; j++) ans1=ans1*(min(a[j].v,l)+j-l)%mod;
            l=i+1;
        }
    printf("%d %d\n",ans1,ans2);
}

[JLOI2013]地形生成

原文：https://www.cnblogs.com/asuldb/p/11078308.html