[51nod1789] 跑得比谁都快
2024-09-01 05:16:15
题面
题解
设\(f[i]\)为根节点到\(i\)的最小耗时
设\(S\)为\(i\)的祖先集合, 可以得到
\[f[i] = min(f[j] + (i - j)^p),j \in S
\]
\]
对于\((i - j)^p\), 我们有
\[((i + 1) - (j + 1))^p + (i - j)^p \leq ((i + 1) - j)^p + (i - (j + 1))^p
\]
\]
可以发现这是一个满足四边形不等式的式子
直接上决策单调性即可(我这个写法是看的别人的, 应该是对的吧)
Code
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#define itn int
#define reaD read
#define N 100005
using namespace std;
int n, p, w[N], cnt;
long long pw[N], ans;
template < typename T >
inline T read()
{
T x = 0, w = 1; char c = getchar();
while(c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
return x * w;
}
namespace Graph
{
int head[N];
struct edge { int to, next; } e[N];
inline void adde(int u, int v) { e[++cnt] = (edge) { v, head[u] }; head[u] = cnt; }
};
using namespace :: Graph;
long long fpow(long long x, int y = p)
{
long long res = 1;
for( ; y; y >>= 1, x = 1ll * x * x)
if(y & 1) res = 1ll * res * x;
return res;
}
namespace DFS
{
long long f[N];
int top, stk[N], pos[N];
struct node { int l, r, id; } q[N];
void dfs(int u, int fa)
{
if(u == 1) stk[++top] = u, f[u] = 0, pos[u] = top;
else
{
int num;
long long tmp = f[0];
for(int i = pos[fa]; i <= top; i++)
{
long long res = f[stk[i]] + w[stk[i]] + fpow(u - stk[i], p);
if(res <= tmp) num = i, tmp = res;
}
f[u] = tmp;
pos[u] = num;
stk[++top] = u;
}
bool flag = 0;
for(int i = head[u]; i; i = e[i].next)
flag = 1, dfs(e[i].to, u);
if(!flag) ans = min(ans, f[u]);
top--;
}
};
using namespace :: DFS;
int main()
{
n = read <int> (); p = read <int> ();
for(int i = 1; i <= n; i++)
{
w[i] = read <int> (); int u = read <int> ();
if(u) adde(u, i);
}
memset(f, 0x3f, sizeof(f));
ans = f[0];
dfs(1, 0);
printf("%lld\n", ans);
return 0;
}
最新文章
- OC编程之道-创建对象之生成器模式
- 邻接表有向图(三)之 Java详解
- 基于HTML5快速搭建3D机房设备面板
- 以HTML为表现的日志记录组件
- HDU 4282 A very hard mathematic problem --枚举+二分(或不加)
- BestCoder Round #85
- [Whole Web] [AngularJS] Localize your AngularJS Application with angular-localization
- Chrome 开发者工具详解(4):Profiles 面板
- 八款强大的jQuery图片滑块动画插件
- lucene&;solr-day1
- Shiro报错-[org.apache.shiro.mgt.AbstractRememberMeManager] - There was a failure while trying to retrieve remembered principals.
- [Codeforces 864E]Fire
- 2.1JAVA基础复习——JAVA语言的基础组成注释和常量变量
- PHP生成PDF文件。
- AT3611 Tree MST
- 4、一、Introduction(入门):3、System Permissions(系统权限)
- How to Conduct High-Impact Research and Produce High-Quality Papers
- linux设置服务器时间同步
- SCM_SVN_CVS
- git(8):常用命令
热门文章
- springcloud eureka注册中心分布式配置
- mvc控制器返回操作结果封装
- Java Web-EL表达式 in JSP
- Docker Registry搭建
- windows连接远程服务器报错&#39;SSH&#39; 不是内部或外部命令,也不是可运行的程序 或批处理文件 解决方案
- C++ DLL导出的两种方式和链接的两种方式
- Spring中事务的传播行为,7种事务的传播行为,数据库事务的隔离级别
- Flutter——ListView组件(平铺列表组件)
- SQLite3学习笔记(2)
- java线程基础巩固---采用多线程方式模拟银行排队叫号以及Runnable接口存在的必要性