「FJ2014集训」愚蠢的算法
问题描述
对于一个1~n的排列{p1,p2,…,pn}，将pi和pj交换，需要的代价为2*|i-j|-1，记f(p)表示通过交换将排列p变成从小到大的排列，即{1,2,3…,n}的最小代价。一个愚蠢的算法是用g(p)=Σmax(0, i-pi)来估算f(p)。给出1~n的排列的前m个元素，求有多少个排列p满足条件f(p)=g(p)。
输入格式
输入n和m，表示1~n的排列，以及确定了前m个数。
接下来一行包含m个数，表示排列中确定的前m个数。
输出格式
输出一行，表示有多少个排列满足条件，输出答案mod 10^9+7。
样例输入1
3 0
样例输出 1
5
样例输入 2
5 2 1 4
样例输出 2
3
数据规模
对于20%的数据，n≤10
对于50%的数据，n≤200
对于100%的数据，n≤2000，m≤n
题解
惊奇的发现，m=0的时候答案序列是卡特兰数列
于是就掉坑里了。。。
先贴个20分暴力。。。
|
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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<cstring> #define ll long long #define inf 1000000000 #define mod 1000000007 using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ans,G; int b[2005]; bool used[2005]; bool jud() { int t=0; for(int i=1;i<=n;i++) for(int j=1;j<i;j++) if(b[j]>b[i])t++; if(t==G)return 1; return 0; } void dfs(int k) { if(k==n+1) { if(jud())ans++; return; } for(int i=1;i<=n;i++) if(!used[i]) { b[k]=i; used[i]=1; G+=max(0,k-b[k]); dfs(k+1); G-=max(0,k-b[k]); used[i]=0; } } void solve1() { for(int i=1;i<=m;i++) { G+=max(0,i-b[i]);used[b[i]]=1; } dfs(m+1); printf("%d\n",ans); } int main() { //freopen("clumsy.in","r",stdin); //freopen("clumsy.out","w",stdout); n=read();m=read(); for(int i=1;i<=m;i++)b[i]=read(); if(n<=10) solve1(); return 0; } |
Subscribe
计数器 9788982
OI 课件=>
OI 课件=>