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