传送门:https://www.luogu.org/problemnew/show/P2467

参考与学习:https://www.luogu.org/blog/user55639/solution-p2467

题意:

  求波动数列

思路:

  设dp【i】【j】 表示长度为i, 开始位子为j, 且开始位子是波峰。

  首先这个波动数列有一些性质:

  1: 在一个波动数列中,若两个 i 与 i+1 不相邻,那么我们直接交换这两个数字就可以组成一个新的波动数列; 举个栗子: 5 2 3 1 4

  2: 把波动数列中的每个数字Ai 变成 (N+1)-Ai 会得到另一个波动数列,且新数列的山峰与山谷情况相反;

  3: 波动序列有对称性。 栗子:1 4 2 5 3 to 3 5 2 1 4

由此可以得到动态规划的递推式:

  dp【i】【j】 =  dp【i】【j-1】+  dp【i-1】【( i - 1 + 1) - j + 1 】

其中,因为 i 和 i+1不相邻,所以可以互换, dp【i】【j】 += dp【i】【j-1】。

或者从 dp【i-1】【j-1】 翻转后推过来,就是dp【i-1】【(i-1+1)- j + 1】。

可以用滚动数组优化

#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert> using namespace std;
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 bll;
typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3;
typedef pair<ll,int>pli;
//priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl '\n' #define OKC ios::sync_with_stdio(false);cin.tie(0)
#define FT(A,B,C) for(int A=B;A <= C;++A) //用来压行
#define REP(i , j , k) for(int i = j ; i < k ; ++i)
#define max3(a,b,c) max(max(a,b), c);
#define min3(a,b,c) min(min(a,b), c);
//priority_queue<int ,vector<int>, greater<int> >que; const ll mos = 0x7FFFFFFF; //
const ll nmos = 0x80000000; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f; //
const int mod = 1e9+;
const double esp = 1e-;
const double PI=acos(-1.0);
const double PHI=0.61803399; //黄金分割点
const double tPHI=0.38196601; template<typename T>
inline T read(T&x){
x=;int f=;char ch=getchar();
while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x=f?-x:x;
}
/*-----------------------showtime----------------------*/ const int maxn = ;
ll dp[][maxn];
int main(){
// freopen("goblin.in", "r", stdin);
// freopen("goblin.out", "w", stdout);
int n,p;
scanf("%d%d", &n, &p);
int id = ;
if(n == ) cout<< % p<<endl;
else {
dp[id][] = ; dp[id][] = ; dp[id][] = ; for(int i=; i<=n; i++){
for(int j=; j<=i; j++){
dp[id^][j] = (dp[id^][j-] + dp[id][i - j + ])%p;
}
id = id ^ ;
}
ll ans = ;
for(int i=; i<=n; i++) ans =(ans + dp[id][i])% p;
printf("%lld\n", ans * % p);
}
return ;
}

最新文章

  1. 虚拟机下CentOS 配置IP地址的三种方法
  2. iOS 让按钮上的标题换行显示
  3. Hibernate4 实例
  4. datatable动态添加,及填充数据
  5. HelloWorld
  6. magento去掉add to cmpre和email to friend
  7. POJ C++程序设计 编程作业—类和对象 编程题 #2
  8. 报名|「OneAPM x DaoCloud」技术公开课:Docker性能监控!
  9. ***总结:在linux下连接redis并进行命令行操作(设置redis密码)
  10. Reso | Noise 网易云音乐插件
  11. python面对对象编程---------6:抽象基类
  12. C# 如何获取错误所在行数
  13. A. Anton and Letters
  14. 【自学php】第二天 - php快速入门
  15. 初探ListView
  16. linux安装jdk8
  17. Windows Server 2012 RS 配置IIS8.0+发布网站
  18. 集合框架-ArrayList,Vector,Linkedlist
  19. java保留小数点两位的4种方法
  20. CentOS6.4 下安装 jdk1.7.0_67

热门文章

  1. (技能篇)双机热备之Oracle切换故障处理
  2. Linux命令之文件相关
  3. 什么是redis的缓存雪崩与缓存穿透
  4. Windows的 IIS 部署django项目
  5. lvs模式及算法
  6. swift 分享share页面封装(功能按钮不同)
  7. npm包开发与发布
  8. 【Java例题】2.1复数类
  9. ibatis 核心原理解析
  10. byte数组和正数BigInteger之间的相互转换