BZOJ1996 [Hnoi2010]chorus 合唱队

时间:2022-09-26 08:55:50

很容易想到区间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 合唱队的更多相关文章

  1. bzoj千题计划211:bzoj1996&colon; &lbrack;Hnoi2010&rsqb;chorus 合唱队

    http://www.lydsy.com/JudgeOnline/problem.php?id=1996 f[i][j][0/1] 表示已经排出队形中的[i,j],最后一个插入的人在[i,j]的i或j ...

  2. BZOJ1996&colon;&lbrack;HNOI2010&rsqb;CHORUS 合唱队&lpar;区间DP&rpar;

    Description Input Output Sample Input 4 1701 1702 1703 1704 Sample Output 8 HINT Solution 辣鸡guide真难用 ...

  3. BZOJ1996&colon; &lbrack;Hnoi2010&rsqb;chorus 合唱队 &lpar;DP&rpar;

    就是想水一发 #include <stdio.h> #include <algorithm> #include <iostream> using namespace ...

  4. 【BZOJ1996】&lbrack;Hnoi2010&rsqb;chorus 合唱队 区间DP

    [BZOJ1996][Hnoi2010]chorus 合唱队 Description Input Output Sample Input 4 1701 1702 1703 1704 Sample Ou ...

  5. bzoj1196:&lbrack;Hnoi2010&rsqb;chorus 合唱队

    这数据范围明显的区间dp啊...然而据说二维会wa...那就写三维把... #include<cstdio> #include<cstring> #include<cct ...

  6. BZOJ 1996&colon; &lbrack;Hnoi2010&rsqb;chorus 合唱队&lpar;dp&rpar;

    简单的dp题..不能更水了.. --------------------------------------------------------------- #include<cstdio&g ...

  7. 【BZOJ】1996&colon; &lbrack;Hnoi2010&rsqb;chorus 合唱队【区间dp】

    1996: [Hnoi2010]chorus 合唱队 Time Limit: 4 Sec  Memory Limit: 64 MBSubmit: 2088  Solved: 1371[Submit][ ...

  8. bzoj 1996&colon; &lbrack;Hnoi2010&rsqb;chorus 合唱队

    Description Input Output Sample Input 4 1701 1702 1703 1704 Sample Output 8 HINT Source 因为只会在区间的两端进行 ...

  9. 【洛谷P3205】&lbrack;HNOI2010&rsqb;CHORUS 合唱队

    合唱队 区间DP f[l][r][0/1]表示生成目标序列中的区间[l,r],最后一个数是a[l]/a[r] 的方案数 边界: f[i][i][0]=1 转移: f[l][r][0]=(a[l]&lt ...

随机推荐

  1. Yii2的urlManager URL美化

    Yii1.*与Yii2中配置路由规则rules是几乎是一样的,但还是有细微的差别. 在Yii1.*中开启path路由规则直接使用 'urlFormat' => 'path', 但在Yii2中已经 ...

  2. svn 1&period;8&period;11 命令行提交新添加文件错误

    由于公司的svn服务器版本不兼容最新的svn 1.8.11导致 提交代码报错 ➜  images  svn ci arrowico.png -m"add images for png ico ...

  3. NM常用网络命令

    Ipconfig命令 Ipconfig命令可以被用来显示机器当前TCP/IP配置信息. 当使用Ipconfig时不带不论什么參数选项,那么它为每一个已经配置好的接口显示IP地址.子网掩码和默认网关值. ...

  4. Asp&period;net MVC 视图使用像Ajax,ViewBag提示为找到上下文

    不知是什么原因,所有的视图中Ajax,ViewBag之类的都提示为找到上下文(由于换了个版本Vs,猜测应该是Vs的原因),然后顺利在网上找到了解决方案. 给地址链接:https://social.ms ...

  5. pwnable&period;tw hacknote

    产生漏洞的原因是free后chunk未置零 unsigned int sub_80487D4() { int index; // [esp+4h] [ebp-14h] char buf; // [es ...

  6. ASP&period;NET&plus;MVC&plus;EntityFramework快速实现增删改查

    本教程已经录制视频,欢迎大家观看我在CSDN学院录制的课程:http://edu.csdn.net/lecturer/944

  7. Transcranial magnetic stimulation &lpar;TMS&rpar;

    Transcranial magnetic stimulation (TMS) Effect of Transcranial Magnetic Stimulation on Free Will Tra ...

  8. 824&period; Goat Latin

    class Solution { public: string toGoatLatin(string S) { S.push_back(' '); //add a space that the loo ...

  9. CDH 5&period;16&period;1 离线部署 &amp&semi; 通过 CDH 部署 Hadoop 服务

    参考 Cloudera Enterprise 5.16.x Installing Cloudera Manager, CDH, and Managed Services Installation Pa ...

  10. Androidの疑难杂症之加载布局报Error inflating class &lt&semi;unknown&gt&semi;

    android.view.InflateException: Binary XML file line #12: Error inflating class <unknown> 出现这种错 ...