惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

C
Check Point Blog
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
L
LangChain Blog
云风的 BLOG
云风的 BLOG
M
MIT News - Artificial intelligence
A
About on SuperTechFans
J
Java Code Geeks
量子位
博客园 - 三生石上(FineUI控件)
博客园 - Franky
博客园_首页
H
Hackread – Cybersecurity News, Data Breaches, AI and More
IT之家
IT之家
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
Apple Machine Learning Research
Apple Machine Learning Research
Engineering at Meta
Engineering at Meta
雷峰网
雷峰网
D
DataBreaches.Net
人人都是产品经理
人人都是产品经理
Martin Fowler
Martin Fowler
有赞技术团队
有赞技术团队
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻

hsfzxjy 的博客

解决 VSCode + CMake + MSVC 编译器信息乱码的问题 使用 3090 部署 1.58bit 动态量化版 DeepSeek R1 671b 如何在 VS Code DevContainer 中配置 HTTP 代理 如何在跳板机背后的服务器上使用 VS Code Remote - Containers Cohesive Digests for Ints and Floats Rust 中的隐匿概念 —— Place(位置) 美术馆 一尺之槌,日取其半,1075日而竭 老生常谈:使用 Cloudflare 自选 IP 加速站点访问 辩义 State、Nation 与 Country 将 Base64 编码的数据快速转换为 Uint8Array 折腾 NPU·第1章 —— 搭建 Level Zero 开发环境 折腾 NPU·第0章 —— Intel NPU 概述与 Level-Zero 新增域名 monad.run CSS 中为特定字符设置不同字体 Arbitary Lifetime Transmutation via Rust Unsoundness Dijkstra 算法的延伸 Manacher 回文计数算法 硬卧 Go Fact: Zero-sized Field at the Rear of a Struct Has Non-zero Size Display *big.Rat Losslessly and Smartly in Golang 代码的仪式 Building Electron From Scratch 中式亲属称谓研究之一:构建半群 Some Notes on Kotlin Coroutines Git sparse-checkout and partial clones for Mega-Repos 辩义“封建” Diving from the CUDA Error 804 into a bug of libnvidia-container Modern Cryptography, GPG and Integration with Git(hub) Move the Root Partition of Ubuntu
UVa12186 Another Crisis && [Dynamic Arrays in Pascal]
2014-09-27 · via hsfzxjy 的博客

链接:Link 耗时:0.586s

昨晚做的太急了,没时间写总结,正好下午有空,补上。

这是一道典型的树形动态规划,不是很难,但十分坑语言。思路大致如下:

对于第 $i$ 个节点,用 $d(i)$ 表示其上诉所需的最小工人数。若 $i$ 为叶节点,则 $d(i)=1$;否则,遍历求出 $i$ 的子节点所对应的 $d$ 值,并由小到大排序,取出最小的几个相加,即为 $d(i)$。

很容易想到用递归来实现。但对于“子节点的 d 值的排序”实现起来却十分困难:因为事先不知道有多少个数。当然啦,如果是 C++ 组,用 vector 可以轻松搞定,可至于 P 党,实现起来却难上加难。思来想去,决定试试 Pascal 的动态数组。磕磕碰碰调了近 1 个小时,终于 AC 了。


var
tree: array [0..100000] of array of int64;
T: Integer;
f: array [0..100000] of int64;
i,l,n,x:longint;

function min(x,y: int64): int64;
begin
if x<y then exit(x) else exit(y);
end;

procedure sort(var arr: array of int64;l,r:longint); overload;
var
i,j:longint;
m,t: int64;
begin
i := l;
j := r;
m := arr[(l+r) >> 1];
repeat
while arr[i]<m do inc(i);
while arr[j]>m do dec(j);
if i<=j then
begin
t := arr[i];
arr[i] := arr[j];
arr[j] := t;
inc(i);
dec(j);
end;
until i>j;
if i<r then sort(arr, i, r);
if l<j then sort(arr, l, j);
end;

procedure sort(var arr: array of int64); overload;
begin
sort(arr, low(arr), high(arr));
end;
function dp(x: longint): int64;
var
arr: array of int64;
l,i, num: longint;
begin
if f[x] <> 0 then
begin
dp := f[x];
exit;
end;
if length(tree[x]) = 0 then
begin
dp := 1;
f[x] := 1;
exit;
end;
l := length(tree[x]);
SetLength(arr, l);
for i := Low(tree[x]) to High(Tree[x]) do
arr[i] := dp(tree[x][i]);
Sort(arr);
num := (l*T-1) div 100+1;
for i := Low(arr) to num-1 do
f[x] := f[x] + arr[i];
dp := f[x];
end;

begin
assign(input, 'main.in');reset(input);
assign(output,'main.out');rewrite(output);
readln(n, T);
while n>0 do
begin
fillchar(f, sizeof(f), 0);
fillchar(tree, sizeof(tree), 0);
for i := 1 to n do
begin
read(x);
SetLength(tree[x], length(tree[x])+1);
tree[x][high(tree[x])] := i;
end;
readln;
dp(0);
writeln(f[0]);
readln(n, T);
end;
close(input); close(output);
end.

Dynamic Arrays

这里,再总结一下动态数组的用法。

  1. 定义:a: array of [type];
  2. 设置长度: SetLength(a, 10);
  3. 长度加一: SetLength(a, Length(a)+1);
  4. 取得最大、最小下标: High(a), Low(a)

事实上,从 1.1 版本开始 FPC 就支持 Dynamic Arrays 了。所以在 NOIP 竞赛中我们大可放心使用。


作者:hsfzxjy
链接:
许可:CC BY-NC-ND 4.0.
著作权归作者所有。本文不允许被用作商业用途,非商业转载请注明出处。