ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[AtCoder Beginner Contest 263]F - Tournament(DFS记忆化搜索 + DP)

2022年8月10日 210点热度 0人点赞 0条评论

题目传送门:F - Tournament (atcoder.jp)

题意 / Problem

有\(2^N\)个人,从\(1 ~ N\)进行编号,进行N轮操作,每轮操作将第\(2i-1\)和第\(2i\)个人进行对战,每次对战都有一个人胜出,失败的人淘汰。

编号为i的人如果赢了j次,那么就可以获得\(C[i][j]\)的奖励。求所有人获得的最大的奖励之和。

思路 / Thought

显然是一颗完美二叉树,容易想到用dfs + 记忆化搜索的方法来进行dp。

那么如何表示状态呢,\(dp[i][j]\)表示编号为i的人,连赢了j次获得的最大奖励和。

dfs的参数为\(o\)树上的节点编号,\(win\)连胜次数。

因为是完美二叉树,所以向下拓展的方式为向左右儿子拓展,若当前节点为o,则左右儿子分别为\(o<<1\)和\(o << 1 | 1\)。

每次向下有两种方式,左赢右输或者左输右赢,取大即可。

递归的终点是当节点编号大于节点数了就返回叶子节点连赢\(win\)次的奖励。

答案就是dfs(1, 0)。

ABC263F

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int c[1 << 17][20], dp[1 << 19][20], N;
//注意dp要开4倍空间
 
int dfs(int o,int win)
{
	if(o >= (1 << N))return c[o - (1 << N) + 1][win];
	if(dp[o][win])return dp[o][win];
	
	int res = 0;
	res = max(dfs(o << 1, win + 1) + dfs(o << 1 | 1, 0), dfs(o << 1, 0) + dfs(o << 1 | 1, win + 1));
	return dp[o][win] = res; 
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	cin >> N;
	for(int i = 1;i <= (1 << N); ++ i)
		for(int j = 1;j <= N; ++ j)
			cin >> c[i][j];
	//input finished
	cout << dfs(1, 0) << '\n';
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: atcoder dfs DP 记忆化搜索
最后更新:2022年8月10日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题意 / Problem
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号