【动态规划】【记忆化搜索】【dfs】bzoj2748 [HAOI2012]音量调节
2024-08-28 20:07:08
f[i][j]表示第i首歌音量为j是否可能。若是将状态之间建边,那么答案就是max(j){f[i][j]==true&&0<=j<=limit}。于是就是图中dfs一遍判断可达性。(<--vis数组也叫记忆化?)
#include<cstdio>
using namespace std;
int n,vis[][],w[],limit,sta;
void dfs(int cur,int now)
{
if(cur>n) return;
vis[cur][now]=;
if(now+w[cur+]<=limit) if(!vis[cur+][now+w[cur+]]) dfs(cur+,now+w[cur+]);
if(now-w[cur+]>=) if(!vis[cur+][now-w[cur+]]) dfs(cur+,now-w[cur+]);
}
int main()
{
scanf("%d%d%d",&n,&sta,&limit);
for(int i=;i<=n;i++) scanf("%d",&w[i]);
dfs(,sta);
for(int i=limit;i>=;--i) if(vis[n][i])
{
printf("%d\n",i);
return ;
}
puts("-1");
return ;
}
最新文章
- Nginx if 条件判断
- OOP的四个魔术方法
- Torch7学习笔记(二)nn Package
- 对于C#中的一些点滴你真的理解了吗?
- 3.发布Maven项目到nexus中
- 异常处理 Exception
- Android经常使用的五种弹出对话框
- HDU 2473 - Junk-Mail Filter ,并查集的删点
- MySQL 复制
- Hive基础(3)---Fetch Task(转)
- AWS的区域和可用区概念解释
- (转)基于微软平台IIS/ASP.NET开发的大型网站有哪些?
- 通俗的理解java设计模式的准则
- ****** 三十四 ******、软设笔记【存储器系统】-Cache存储器
- html一些标签在不同浏览器或者不同版本浏览器的注意事项
- 分区实践 注意分区名 p2018-01 p2018-02 被解释为同一分区名
- 1-10假期训练(hdu-2059 简单dp)
- 【Python学习笔记】使用python进行kmeans聚类
- EM 最大似然概率估计
- 【最大独立集】BZOJ3175- [Tjoi2013]攻击装置