首页 > 代码库 > BZOJ1925 SDOI2010 地精部落 一般DP
BZOJ1925 SDOI2010 地精部落 一般DP
题意：求1-N组成的长度为N的数列中，除了两端外，中间任意一个位置i均满足（ai-1＜ai &&ai+1＜ai）或（ai-1>ai && ai+1>ai）题解：考场上遇到这种题果断暴力设f[i][j]为1-i组成的数列，1-j其中一个为开头，且开头为山峰的方案数，转移分为两部分：
f[i][j-1]：不选j为开头
f[i-1][i-j+1]：选j为开头，剩下i-1个数，为了保证下降，第二个数一定是1-(j-1)，由于f记录的是开头为山峰的方案数，所以需要取反，也就是(i-1)-(j-1)+1=i-j+1
初始化f[2][2]=1，由于题目卡内存，所以需要滚动数组。
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;const int MAXN=4200+2;int N,P,f[2][MAXN];int main(){ cin >> N >> P; f[0][2]=1; for(int i=3;i<=N+1;i++) for(int j=1;j<=i;j++) f[i&1][j]=(f[!(i&1)][i-j+1]+f[i&1][j-1])%P; cout << f[(N+1)&1][N+1]*2%P << endl; return 0;}
BZOJ1925 SDOI2010 地精部落 一般DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。