SGU 489

就是说一个1到n的排列如果是一上一下的。。那么就叫local extreme。。

然后告诉你n让你求1到n的排列里local extream的数量。。

我太无耻了。。首先暴力搜出1到8的结果。。

1,2,4,10,32,122,544,2770

然后上www.research.att.com/~njas/sequences/index.html

搜索这个数列。。然后找到了这个数列的介绍mathworld.wolfram.com/AlternatingPermutation.html

然后用http://mathworld.wolfram.com/EulerZigzagNumber.html上面的办法来做的。。

说实话我根本没有搞懂这个是什么意思!但是我还是写了程序。。A掉了这道题。。

以后遇到数列题就这么干了。。话说我发现SGU上过了100题了。。高兴一下

Code:

#include<cstdio>#include<iostream>#include<algorithm>#include<string>#include<vector>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=10000+10;int dp[2][maxn]={0};int main(){ //freopen("in","r",stdin); int n,m;cin>>n>>m;–n;if(!n){cout<<1%m<<endl;return 0;} int now=0,old=1; dp[now][1]=1; for(int i=2;i<=n;i++) { swap(now,old); dp[now][0]=0; for(int j=1;j<=n;j++) { dp[now][j]=dp[now][j-1]; if(i>j) { dp[now][j]+=dp[old][i-j]; if(dp[now][j]>=m) dp[now][j]-=m; } } } int ans=0; for(int i=1;i<=n;i++) ans+=dp[now][i],ans%=m; cout<<(ans*2)%m<<endl;}

本高亮代码使用codeHl生成,查看详情

PS。。我总算搞明白这个公式了


E(n,k)是1到n的排列中第一个是k且一开始下降的数量。。
由于是下降,那么下一个要小于k。。
那么如果下一个是k-1的话。。
那么就是剩下的数列第一个是k-1并且上升的方法数了。。
由于k已经选了。。那么k-1在这个数列中是倒数第n-k个。。
上升跟下降是11对应的。。于是这方面的是E(n-1,n-k)。。
然后如果下一个不是k。。那么就是E(n,k-1)了。。
加起来就是上面的公式
这个里面第一个是下降。。最后答案乘以2。。。。
因此要特判n=1的情况。。

3 thoughts on “SGU 489

  1. 有一个地方看不懂耶。。然后如果下一个不是k。。那么就是E(n,k-1)了。。这是什么意思?为什么有E(n,k-1)种?

  2. E(n,k)是1到n的排列中第一个是k且一开始下降的数量。。我认为这个理解应该不对,因为E(n,n)=0,而E(n,1)不为0……另外k貌似不是指具体数值,只是代表相对大小,可理解为第k大..不过暂时未确定是第k大还是第k小…= =

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>