bzoj 1996 区间dp
2024-09-01 15:38:42
1996: [Hnoi2010]chorus 合唱队
Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 1727 Solved: 1115
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
4
1701 1702 1703 1704
1701 1702 1703 1704
Sample Output
8
HINT
要想知道[l,r]的初始队形的方案数,如果我们知道[l,r-1]和[l+1,r]有几种初始方案的话似乎就可以转移了,但是还是有点问题,我们如何判断不在区间里的那个元素前面的元素的值,根据大或者小往前面或后面插入,如果不知道相对大小似乎不可行,我们可以多开一维记录最后一个元素的位置,只有两种开头或者结尾。
但要注意初始化时对于dp[i][i][0]和dp[i][i][1]只要有一个为零就好了,否则会出现重复的转移,单个元素没什么前后之分。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mod 19650827
int dp[][][];
int a[];
int f(int l,int r,int x)
{
if(dp[l][r][x]!=-) return dp[l][r][x];
if(l==r) return x;
int res=;
if(x){
if(a[r]>a[r-]) res=(res+f(l,r-,));
if(a[r]>a[l]) res=(res+f(l,r-,));
}
else{
if(a[l]<a[r]) res=(res+f(l+,r,));
if(a[l]<a[l+]) res=(res+f(l+,r,));
}
return dp[l][r][x]=res%mod;
}
int main()
{
int N,i,j,k,s;
scanf("%d",&N);
for(i=;i<=N;++i) scanf("%d",a+i);
memset(dp,-,sizeof(dp));
printf("%d\n",(f(,N,)+f(,N,))%mod);
return ;
}
最新文章
- GitHub 基本常用知识解答
- 运行编译后的程序报错 error while loading shared libraries: lib*.so: cannot open shared object file: No such file or directory
- Javascript设计模式之我见:迭代器模式
- 第五周&;第六周
- .net中判断距离高考多长时间的js函数
- 三大文本处理工具grep、sed及awk的简单介绍
- 数学类杂志SCI2013-2014影响因子
- Spark RDD/Core 编程 API入门系列 之rdd案例(map、filter、flatMap、groupByKey、reduceByKey、join、cogroupy等)(四)
- 跨域请求,关于后端session会话丢失的解决办法
- Linux怎样修改系统时间
- python-整理--使用IDE
- AngularJS初始用之 中间件 connect .static 静态文件不能找到
- head first--------------------template method pattern
- 如何理解Spring IOC
- Linux搭建git服务端
- js jquery 正则去空字符
- Spring Data Solr入门
- ffmpeg录制流媒体,正常方式停止录制
- xenserver开启虚拟机时提示找不到存储介质,强制关闭和重启都没用
- 进制转换&;数据类型(1)
热门文章
- Java中的编码乱码问题
- Web UI 自动化单个xpath抓取插件详解
- CDOJ 1287 MC挖矿世界(Spfa+set优化)
- CCF 权限查询(模拟)
- XVII Open Cup named after E.V. Pankratiev Stage 14, Grand Prix of Tatarstan, Sunday, April 2, 2017 Problem J. Terminal
- Winter-1-C A + B II 解题报告及测试数据
- 某个php爬虫程序分析--来自wooyun
- linux pip 查看版本提示
- 如何交叉编译Python到ARM-Linux平台(转)
- cl.exe 命令行编译sqlite3 sqlite3.dll及sqlite3.exe