很容易想到区间DP
然后发现这个区间只和圆序列的最后一个数有关,而原序列的最后一个数只可能是现在区间的头或者尾
令$f[i][j][0/1]$表示在区间$[i, j]$之间,原序列的最后一个数是当前区间的头/尾的总答案数
于是只要讨论$a[i], a[i + 1], a[j - 1], a[j]$之间的关系搞一搞就可以了
/**************************************************************
Problem: 1996
User: rausen
Language: C++
Result: Accepted
Time:112 ms
Memory:8700 kb
****************************************************************/ #include <cstdio>
#include <cstring> using namespace std;
const int N = (int) 1e3 + ;
const int mod = ; int n, a[N];
int f[N][N][], ans; int main() {
int i, j, len;
scanf("%d", &n);
if (n == ) {
puts("");
return ;
}
for (i = ; i <= n; ++i) scanf("%d", a + i);
for (i = ; i < n; ++i)
f[i][i + ][] = f[i][i + ][] = bool(a[i] < a[i + ]);
for (len = ; len <= n; ++len)
for (i = ; i <= n - len + ; ++i) {
j = i + len - , f[i][j][] = f[i][j][] = ;
if (a[j] > a[j - ]) f[i][j][] += f[i][j - ][];
if (a[j] > a[i]) f[i][j][] += f[i][j - ][];
if (a[i] < a[i + ]) f[i][j][] += f[i + ][j][];
if (a[i] < a[j]) f[i][j][] += f[i + ][j][];
f[i][j][] %= mod, f[i][j][] %= mod;
}
ans = (f[][n][] + f[][n][]) % mod;
printf("%d\n", ans);
return ;
}
BZOJ1996 [Hnoi2010]chorus 合唱队的更多相关文章
-
bzoj千题计划211:bzoj1996: [Hnoi2010]chorus 合唱队
http://www.lydsy.com/JudgeOnline/problem.php?id=1996 f[i][j][0/1] 表示已经排出队形中的[i,j],最后一个插入的人在[i,j]的i或j ...
-
BZOJ1996:[HNOI2010]CHORUS 合唱队(区间DP)
Description Input Output Sample Input 4 1701 1702 1703 1704 Sample Output 8 HINT Solution 辣鸡guide真难用 ...
-
BZOJ1996: [Hnoi2010]chorus 合唱队 (DP)
就是想水一发 #include <stdio.h> #include <algorithm> #include <iostream> using namespace ...
-
【BZOJ1996】[Hnoi2010]chorus 合唱队 区间DP
[BZOJ1996][Hnoi2010]chorus 合唱队 Description Input Output Sample Input 4 1701 1702 1703 1704 Sample Ou ...
-
bzoj1196:[Hnoi2010]chorus 合唱队
这数据范围明显的区间dp啊...然而据说二维会wa...那就写三维把... #include<cstdio> #include<cstring> #include<cct ...
-
BZOJ 1996: [Hnoi2010]chorus 合唱队(dp)
简单的dp题..不能更水了.. --------------------------------------------------------------- #include<cstdio&g ...
-
【BZOJ】1996: [Hnoi2010]chorus 合唱队【区间dp】
1996: [Hnoi2010]chorus 合唱队 Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 2088 Solved: 1371[Submit][ ...
-
bzoj 1996: [Hnoi2010]chorus 合唱队
Description Input Output Sample Input 4 1701 1702 1703 1704 Sample Output 8 HINT Source 因为只会在区间的两端进行 ...
-
【洛谷P3205】[HNOI2010]CHORUS 合唱队
合唱队 区间DP f[l][r][0/1]表示生成目标序列中的区间[l,r],最后一个数是a[l]/a[r] 的方案数 边界: f[i][i][0]=1 转移: f[l][r][0]=(a[l]< ...
随机推荐
-
Yii2的urlManager URL美化
Yii1.*与Yii2中配置路由规则rules是几乎是一样的,但还是有细微的差别. 在Yii1.*中开启path路由规则直接使用 'urlFormat' => 'path', 但在Yii2中已经 ...
-
svn 1.8.11 命令行提交新添加文件错误
由于公司的svn服务器版本不兼容最新的svn 1.8.11导致 提交代码报错 ➜ images svn ci arrowico.png -m"add images for png ico ...
-
NM常用网络命令
Ipconfig命令 Ipconfig命令可以被用来显示机器当前TCP/IP配置信息. 当使用Ipconfig时不带不论什么參数选项,那么它为每一个已经配置好的接口显示IP地址.子网掩码和默认网关值. ...
-
Asp.net MVC 视图使用像Ajax,ViewBag提示为找到上下文
不知是什么原因,所有的视图中Ajax,ViewBag之类的都提示为找到上下文(由于换了个版本Vs,猜测应该是Vs的原因),然后顺利在网上找到了解决方案. 给地址链接:https://social.ms ...
-
pwnable.tw hacknote
产生漏洞的原因是free后chunk未置零 unsigned int sub_80487D4() { int index; // [esp+4h] [ebp-14h] char buf; // [es ...
-
ASP.NET+MVC+EntityFramework快速实现增删改查
本教程已经录制视频,欢迎大家观看我在CSDN学院录制的课程:http://edu.csdn.net/lecturer/944
-
Transcranial magnetic stimulation (TMS)
Transcranial magnetic stimulation (TMS) Effect of Transcranial Magnetic Stimulation on Free Will Tra ...
-
824. Goat Latin
class Solution { public: string toGoatLatin(string S) { S.push_back(' '); //add a space that the loo ...
-
CDH 5.16.1 离线部署 &; 通过 CDH 部署 Hadoop 服务
参考 Cloudera Enterprise 5.16.x Installing Cloudera Manager, CDH, and Managed Services Installation Pa ...
-
Androidの疑难杂症之加载布局报Error inflating class <;unknown>;
android.view.InflateException: Binary XML file line #12: Error inflating class <unknown> 出现这种错 ...