首页 > 代码库 > BZOJ 3193 地形生成
BZOJ 3193 地形生成
这种dp好烦啊。
懒得写题解。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 1050 #define mod 2011 using namespace std; int n,x,y,f[maxn],ans1=1,ans2=1,l[maxn],r[maxn],cnt=0; struct status { int h,f; friend bool operator < (const status &x,const status &y) { if (x.h!=y.h) return x.h>y.h; return x.f<y.f; } }s[maxn]; int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d%d",&s[i].h,&s[i].f); sort(s+1,s+n+1); for (int i=1;i<=n;i++) { if (s[i].h!=s[i-1].h) { r[cnt]=i-1; l[++cnt]=i; } } r[cnt]=n; for (int i=1;i<=cnt;i++) { for (int j=l[i];j<=r[i];j++) ans1=(ans1*min(s[j].f+j-l[i],j))%mod; memset(f,0,sizeof(f));f[1]=1; for (int j=l[i];j<=r[i];j++) for (int k=1;k<=min(s[j].f,l[i]);k++) f[k]=(f[k]+f[k-1])%mod; int ret=0;for (int k=1;k<=min(s[r[i]].f,l[i]);k++) ret=(ret+f[k])%mod; ans2=(ans2*ret)%mod; } printf("%d %d\n",ans1,ans2); return 0; }
BZOJ 3193 地形生成
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。