首页 > 代码库 > 【动态规划】【记忆化搜索】【dfs】bzoj2748 [HAOI2012]音量调节
【动态规划】【记忆化搜索】【dfs】bzoj2748 [HAOI2012]音量调节
f[i][j]表示第i首歌音量为j是否可能。若是将状态之间建边，那么答案就是max(j){f[i][j]==true&&0<=j<=limit}。于是就是图中dfs一遍判断可达性。(<--vis数组也叫记忆化？)
1 #include<cstdio> 2 using namespace std; 3 int n,vis[51][1001],w[51],limit,sta; 4 void dfs(int cur,int now) 5 { 6 if(cur>n) return; 7 vis[cur][now]=1; 8 if(now+w[cur+1]<=limit) if(!vis[cur+1][now+w[cur+1]]) dfs(cur+1,now+w[cur+1]); 9 if(now-w[cur+1]>=0) if(!vis[cur+1][now-w[cur+1]]) dfs(cur+1,now-w[cur+1]);10 }11 int main()12 {13 scanf("%d%d%d",&n,&sta,&limit);14 for(int i=1;i<=n;i++) scanf("%d",&w[i]);15 dfs(0,sta);16 for(int i=limit;i>=0;--i) if(vis[n][i])17 {18 printf("%d\n",i);19 return 0;20 }21 puts("-1");22 return 0;23 }
【动态规划】【记忆化搜索】【dfs】bzoj2748 [HAOI2012]音量调节
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。