【bzoj1925】地精部落[SDOI2010]（dp）
题目传送门：1925: [Sdoi2010]地精部落这道题，，，首先可以一眼看出他是要我们求由1~n的排列组成，并且抖来抖去的序列的方案数。然后再看一眼数据范围，，，似乎是O(n^2)的dp？然后各种撕烤，，，然而还是不会。。。对于这道题，我第一眼的想法是用f[i][j]表示长度为i，最后一个数是j...
bzoj 1925: [Sdoi2010]地精部落
Description传说很久以前，大地上居住着一种神秘的生物：地精。 地精喜欢住在连绵不绝的山脉中。具体地说，一座长度为 N 的山脉 H可分 为从左到右的 N 段，每段有一个独一无二的高度 Hi，其中Hi是1到N 之间的正 整数。 如果一段山脉比所有与它相邻的山脉都高，则这段山脉是一个山峰。位于边...
bzoj1925&&luogu2467 地精部落
http://www.elijahqi.win/archives/539 题目描述 传说很久以前，大地上居住着一种神秘的生物：地精。 地精喜欢住在连绵不绝的山脉中。具体地说，一座长度为N的山脉H可分为从左到右的N段，每段有一个独一无二的高度Hi，其中Hi是1到N之间的正整数。 如果一段山...
【BZOJ】1925: [Sdoi2010]地精部落 DP+滚动数组
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1925题意:输入一个数N(1 <= N <= 4200),问将这些数排列成折线型有多少中合法的排列；折线形即一个数比相邻的数都大或者都小;如:1 3 2 4就是一个折线型；思路:f...
bzoj 1925 dp
思路：dp[ i ][ 0 ]表示第一个是山谷的方案，dp[ i ][ 1 ]表示第一个是山峰的方案， 我们算dp[ x ][ state ]的时候枚举 x 的位置x 肯定是山峰， 然后就用组合数算方案就好啦。卡空间 模数是1e9 不是 109 巨坑。#include<bits/stdc++....