首页 > 代码库 > [Sdoi2010]地精部落
[Sdoi2010]地精部落
1925: [Sdoi2010]地精部落
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 1300 Solved: 800
[Submit][Status][Discuss]
Description
传说很久以前，大地上居住着一种神秘的生物：地精。 地精喜欢住在连绵不绝的山脉中。具体地说，一座长度为 N 的山脉 H可分 为从左到右的 N 段，每段有一个独一无二的高度 Hi，其中Hi是1到N 之间的正 整数。 如果一段山脉比所有与它相邻的山脉都高，则这段山脉是一个山峰。位于边 缘的山脉只有一段相邻的山脉，其他都有两段（即左边和右边）。 类似地，如果一段山脉比所有它相邻的山脉都低，则这段山脉是一个山谷。 地精们有一个共同的爱好——饮酒，酒馆可以设立在山谷之中。地精的酒馆 不论白天黑夜总是人声鼎沸，地精美酒的香味可以飘到方圆数里的地方。 地精还是一种非常警觉的生物，他们在每座山峰上都可以设立瞭望台，并轮 流担当瞭望工作，以确保在第一时间得知外敌的入侵。 地精们希望这N 段山脉每段都可以修建瞭望台或酒馆的其中之一，只有满足 这个条件的整座山脉才可能有地精居住。 现在你希望知道，长度为N 的可能有地精居住的山脉有多少种。两座山脉A 和B不同当且仅当存在一个 i，使得 Ai≠Bi。由于这个数目可能很大，你只对它 除以P的余数感兴趣。
Input
仅含一行，两个正整数 N, P。
Output
仅含一行，一个非负整数，表示你所求的答案对P取余 之后的结果。
Sample Input
4 7
Sample Output
3
HINT
对于 20%的数据，满足 N≤10；
对于 40%的数据，满足 N≤18；
对于 70%的数据，满足 N≤550；
对于 100%的数据，满足 3≤N≤4200，P≤109
Source
第一轮Day2
/*Orz 魏铭。想出来满分做法。。但是只能70分。首先，设状态f[i][H][0/1]表示序列posi是H，且为山峰/山谷。然后转移很显然。不过实现只能强打记忆化搜索。为什么呢？因为他是一个排列。转递推就要状压。就是用bitset也会爆。抛开空间不讲。时间也过不了。为什么？转移时O(n)的。如何优化？用前缀和优化变为O(1)。在处理好空间且保证状态正确的前提下，转成递推，用前缀和转移就好了。当时也想到了，但，写不出来。当场 魏铭 就用一种很神奇的方法，解决了我的问题，然，我还是看不懂。码力太弱了。。。此题对我感触很大。思维：从裸暴力->状压剪枝->换状态->换状态->换状态->优化->正解思路≠>正解代码（码力弱）。*/#include<cstdio>#include<cstring>#include<algorithm>#define set(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);using namespace std;typedef long long ll;const int N=555;int n,vis[N];ll f[N][N][2];ll ans,mod;//d=1 high//d=0 lowll dfs(int cur,int h,bool d){ ll &res=f[cur][h][d]; if(~res) return res; res=0; if(cur>=n) return res=1; if(d){ for(int i=1;i<h;i++){ if(!vis[i]){ vis[i]=1; res+=dfs(cur+1,i,!d); vis[i]=0; } } } else{ for(int i=h+1;i<=n;i++){ if(!vis[i]){ vis[i]=1; res+=dfs(cur+1,i,!d); vis[i]=0; } } } return res%=mod;}inline void DFS(){ for(int i=1;i<=n;i++){ vis[i]=1; dfs(1,i,0); dfs(1,i,1); vis[i]=0; } for(int i=1;i<=n;i++){ ans=(ans+f[1][i][0]+f[1][i][1])%mod; }}int main(){ set(goblin); memset(f,-1,sizeof f); scanf("%d%I64d",&n,&mod); if(n==1){printf("%I64d",1LL%mod);} if(mod==1){printf("0");} DFS(); printf("%I64d",ans); return 0;} /*附魏铭100分代码#include <stdio.h>#include <string.h>#include <stdlib.h>#include <iostream>using namespace std;#define zbwmqlw#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define abs(x) ((x)>0?(x):-(x))#define pow(x) (1<<(x))const int inf=0x3f3f3f3f;typedef __int64 LL;template<class T> void checkmin(T &a,const T &b) {if (b<a) a=b;}template<class T> void checkmax(T &a,const T &b){if (b>a) a=b;}const int N=4300;int a[20];bool vis[20],now,last;int n,ans;LL f[2][N][2],mo;void dfs(int depth){ if (depth==n+1) { ++ans; return; } int i; for (i=1;i<=n;++i) if (!vis[i]) { a[depth]=i; if (depth>2 && (a[depth]>a[depth-1])==(a[depth-1]>a[depth-2])) continue; vis[i]=true; dfs(depth+1); vis[i]=false; }}void solvedfs(){ ans=0; dfs(1); printf("%d %d\n",n,ans); exit(0);}void solvedp(){ int i,j,k; now=true; last=false; memset(f[now],0,sizeof(f[now])); for (j=0;j<n;++j) f[now][j][0]=f[now][j][1]=1; for (i=2;i<=n;++i) { now^=1; last^=1; memset(f[now],0,sizeof(f[now])); LL s0=0,s1=0; for (k=0;k+i-1<=n;++k) s1+=f[last][k][1]; for (j=0;j+i<=n;++j) { s0+=f[last][j][0]; s1-=f[last][j][1]; f[now][j][1]=s0%mo; f[now][j][0]=s1%mo; } } printf("%I64d\n",(f[now][0][0]+f[now][0][1])%mo);}int main(){ freopen("goblin.in","r",stdin); freopen("goblin.out","w",stdout); scanf("%d%I64d",&n,&mo); solvedp(); fclose(stdout);}*/
AC思路：http://blog.csdn.net/mrazer/article/details/53426415?locationNum=12&fps=1
#include<cstdio>#define set(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);using namespace std;const int N=4201;int f[2][N],n,now,mod,ans;int main(){ set(goblin); scanf("%d%d",&n,&mod); f[now][1]=1; for(int i=2;i<=n;i++){ now^=1; for(int j=1;j<=i;j++){ f[now][j]=(f[now][j-1]+f[now^1][i-j+1])%mod; } } for(int i=1;i<=n;i++) ans=(ans+f[now][i])%mod; printf("%d\n",ans*2%mod); return 0;}
[Sdoi2010]地精部落
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。