首先每个学校的界限范畴是\(1e9\)，必定不能直接\(dp[i][j]\)暗示前i所学校，第\(i\)所学校派出\(j\)艘船，，但\(b<=500\)所有考虑把\(a,b\)离散，第二维改为当前这个学校派出数量在阿谁区间里
转移的时候，如果前面所有的学校都不在此区间内，那孝敬为\(\sum_{i‘=1}^{i}\sum_{j‘=1}^{j}dp[i‘][j‘]\)
但是如果有学校要选在该区间内，问题便转化为在一段长度为len的区间内选出k个数，使他们递增，固然，有些数是可以不选的，该方案数为\(\sum_{i=0}^{k}C(k,k-i)*C(len,i)\),这个对象看起来一点都欠好算,我们把这个式子化为\(C(len+k,k)\)
所以如果此刻是第i个学校到第k个学校在此范畴内，并且i,k学校强制选择，则方案数为\(C(i-k-1+len,i-k-1)\),孝敬为\(\sum_{i‘=i-1}^{1}C(len+i-i‘-1,i-i‘-1)\sum_{k=1}^{i‘-1}\sum_{j‘=1}^{j-1}dp[k][j‘]\)此中&j&是当前枚举的区间
对付每一段区间，\(len\)不异，所以我们在枚举区间是措置惩罚惩罚一下组合数，后面的两重循环用前缀和措置惩罚惩罚一下，时间庞大度\(O(n^3)\)
#include<bits/stdc++.h> using namespace std; typedef int sign; typedef long long ll; #define For(i,a,b) for(register sign i=(sign)a;i<=(sign)b;++i) #define Fordown(i,a,b) for(register sign i=(sign)a;i>=(sign)b;--i) const int N=500+5; bool cmax(sign &a,sign b){return (a<b)?a=b,1:0;} bool cmin(sign &a,sign b){return (a>b)?a=b,1:0;} template<typename T>T read() { T ans=0,f=1; char ch=getchar(); while(!isdigit(ch)&&ch!=‘-‘)ch=getchar(); if(ch==‘-‘)f=-1,ch=getchar(); while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-‘0‘),ch=getchar(); return ans*f; } template<typename T>void write(T x,char y) { if(x==0) { putchar(‘0‘);putchar(y); return; } if(x<0) { putchar(‘-‘); x=-x; } static char wr[20]; int top=0; for(;x;x/=10)wr[++top]=x%10+‘0‘; while(top)putchar(wr[top--]); putchar(y); } void file() { #ifndef ONLINE_JUDGE freopen("3643.in","r",stdin); freopen("3643.out","w",stdout); #endif } int n,a[N],b[N],l[N<<1],tot; void input() { n=read<int>(); For(i,1,n) { a[i]=read<int>(),b[i]=read<int>(); l[++tot]=a[i],l[++tot]=b[i]+1; } } void init() { sort(l+1,l+tot+1); tot=unique(l+1,l+tot+1)-l-1; For(i,1,n) { a[i]=lower_bound(l+1,l+tot+1,a[i])-l; b[i]=lower_bound(l+1,l+tot+1,b[i]+1)-l; } } const int mo=1e9+7; int inv[N],dp[N],C[N]; void work() { int len; inv[1]=1;For(i,2,n)inv[i]=1ll*(mo-mo/i)*inv[mo%i]%mo; C[0]=dp[0]=1; For(i,1,tot-1) { len=l[i+1]-l[i]; For(i,1,n)C[i]=1ll*C[i-1]*(len+i-1)%mo*inv[i]%mo; Fordown(j,n,1)if(a[j]<=i&&i+1<=b[j]) { int f=0,pos=1,c=len; Fordown(k,j-1,0) { (f+=1ll*dp[k]*c%mo)%=mo; if(a[k]<=i&&i+1<=b[k])c=C[++pos]; } (dp[j]+=f)%=mo; } } int ans=0; For(i,1,n)(ans+=dp[i])%=mo; write(ans,‘\n‘); } int main() { file(); input(); init(); work(); return 0; }
APIO2016赛艇
标签：
原文地点：https://www.cnblogs.com/dengyixuan/p/8881136.html