题解 P3205 【[HNOI2010]合唱队】
2024-09-06 21:11:30
讲讲我的做法
看了题目发现要用区间\(dp\),为什么?
我们发现区间\(dp\)有一个性质——大区间包涵小区间,这道题就符合这样的一个性质
所以我们要用区间\(dp\)来解决这道题。
如何设计状态
那么我们要怎么设计状态,我们想,每给人进入队伍里,只有2种可能,1种是从左边加入,另外1种是从右边进入,所以我们的装态是有3个数
\(f[i][j][0]\)表示的是第\(i\)人从左边进来的方案数
\(f[i][j][1]\)表示的是第\(j\)人从右边进来的方案数
推导状态转移方程
从左边进来肯定前1个人比他高,前1个人有2种情况,要么在\(i+1\)号位置,要么在\(j\)号位置。
同理
从右边进来肯定前1个人比他矮,前1个人有2种情况,要么在\(j-1\)号位置,要么在\(i\)号位置。
那么状态转移方程就出来了
if(a[i]<a[i+1])f[i][j][0]+=f[i+1][j][0];
if(a[i]<a[j])f[i][j][0]+=f[i+1][j][1];
if(a[j]>a[i])f[i][j][1]+=f[i][j-1][0];
if(a[j]>a[j-1])f[i][j][1]+=f[i][j-1][1];
f[i][j][0]%=19650827;
f[i][j][1]%=19650827;
边界条件
当\(i=j\)的时候显然只有一种方案,所以边界条件是
for(int i=1;i<=n;i++)f[i][i][0]=1,f[i][i][1]=1;
然而你会发现你WA了,为什么
因为,只有一个人的时候方案只有一种,可是我们这里却有2种方案,所以我们得默认1个人的时候,是从左边进来,于是我们就有了正确的边界条件
for(int i=1;i<=n;i++)f[i][i][0]=1;
完整代码
#include <bits/stdc++.h>
using namespace std;
int f[2010][2010][2],a[2010];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)f[i][i][0]=1;
for(int len=1;len<=n;len++)
for(int i=1,j=i+len;j<=n;i++,j++){
if(a[i]<a[i+1])f[i][j][0]+=f[i+1][j][0];
if(a[i]<a[j])f[i][j][0]+=f[i+1][j][1];
if(a[j]>a[i])f[i][j][1]+=f[i][j-1][0];
if(a[j]>a[j-1])f[i][j][1]+=f[i][j-1][1];
f[i][j][0]%=19650827;
f[i][j][1]%=19650827;
}
cout<<(f[1][n][0]+f[1][n][1])%19650827;
return 0;
}
最新文章
- 挑子学习笔记:对数似然距离(Log-Likelihood Distance)
- Android开发资源汇总
- [转]在 ASP.NET MVC 4 中创建为移动设备优化的视图
- 路由系统的核心对象——Router
- 常见linux命令释义(第二天)
- sqlmap写文件为空之谜
- Android接口传递Json数组的处理方式
- 网站启动SSL, http变为https后,session验证码错误解决方法
- Codevs 1010 过河卒 2002年NOIP全国联赛普及组
- Android学习之 WebView使用小结
- day45-python实例练习
- Galaxy2D Game Engine 4.2 开发版发布
- python基础自学 第一天
- Bean named &#39;...&#39; is expected to be of type [...] but was actually of type [com.sun.proxy.$Proxy7解决方法
- Atlassian JavaScript load error(配置Atlassian的时候报无法加载script文件)
- IDA远程调试 在内存中dump Dex文件
- JD m站自我解析理解
- 【转】高效率编辑器VIM
- SQLite的升级(转)
- win7编程接口的一些变化
热门文章
- ActiveMQ此例简单介绍基于docker的activemq安装与集群搭建
- 高阶函数---swift中的泛型介绍(一步步实现Map函数)
- 制作UEFI(64位)下的WinPE + Ubuntu + Acronis多启动U盘
- USB小白学习之路(11) Cy7c68013A驱动电路设计注意事项(转)
- webpack 手动创建项目
- CMSampleBufferRef解析
- Java设计模式之结构模式
- Xcode辅助工具之热重载插件利器
- Ubuntu16.04下安装python3.6.4详细步骤
- docker 学习路线