洛谷 P2467 地精部落 题解
2024-10-07 05:39:58
好难啊好难啊好难啊~(以后再玩魔兽的时候绝对绝对虐死他)
做完后总结了一下思路;
首先推一下以下三条性质:
1.若两个 i 与 i+1 不相邻,那么我们直接交换这两个数字就可以组成一个新的数列 (这一条便是我们状态转移的依据)
2.每个数字ai 变成 (n+1)-ai 会得到另一个数列,且新数列的山峰与山谷情况相反
3.波动序列有对称性。 举个例子:1 4 2 5 3 变为 3 5 2 1 4
设f[i][j]表示从1~i中第1个数为j是的状态有多少种;
根据性质1,当j与j-1不相邻时,f[i][j]=f[i][j-1]
当j与j-1相邻的时候 ,f[i][j]就是求 i-1个数,j-1为头,但是j-1 为山谷的方案数
根据性质2,( i-1个数,j-1为头,但是j-1 为山谷的方案数)等价于求((i-1个数,((i-1)+1)-(j-1))为头,j-1为山峰的方案数);
那么f[i][j]=f[i-1][i-j-1];
综上所述,f[i][j]=f[i][j-1]+f[]i-1][i-j-1];
由于数据比较水的原因,内存提供的足够多,二维数组完全可以AC掉。
#include <bits/stdc++.h>
using namespace std;
int f[][];
int main()
{
int n,p;
cin>>n>>p;
f[][]=;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(i-j->=) f[i][j]=f[i][j-]+f[i-][i-j-];
f[i][j]%=p;
}
}
long long ans=;
for(int i=;i<=n;i++) ans=(ans+f[n][i])%p;
cout<<(ans*)%p;
}
最新文章
- 洛谷P1991无线通讯网[kruskal | 二分答案 并查集]
- Azure
- request.getHeader所想到的
- session没有过期,其保存的数据无故丢失的原因
- freemodbus线圈中的位操作
- Angularjs中编写指令模版
- K3精益版给物料添加属性,并在BOM中新增字段引用该属性
- lvs为何不能完全替代DNS轮询
- [转]通过设置nginx的client_max_body_size解决nginx+php上传大文件的问题
- 【代码笔记】Web-ionic-安装及第一个app
- HTML5 本地文件操作之FileSystemAPI实例(一)
- pyqt、webkit和qt之间的关系
- SAP NetWeaver BW 7.3介绍
- maven 使用之自动编译热部署设置
- Java常用的加密解密类(对称加密类)
- Oracle 的PL/SQL语言使用
- 【服务器防护】centos iptables 防火墙设置 mac过滤
- Python入门 —— 06语音识别
- 如何把C盘里的文件默认位置更改到D盘指定目录?
- 2017Nowcoder Girl初赛重现赛