~ Esoteria Algorithm in Reverse Observatory

LGOJ P1254 | 扇区填数

Portal

有一个圆,当输入一个整数 n(1n8)n(1\leq n\leq 8) 后,它被分成 nn 个扇区。

所以圆中有 nn 条分割线。从圆中选取 2 条分割线,可以将圆分割为由连续扇区组成的两部分。又选择所有扇区是被允许的,所以:

i2Cn2+1=n2n+1i\leq 2\cdot C_n^2 +1=n^2-n+1

因为 n8n\leq 8 ,所以 i57i\leq 57。但通过手算,可以 大胆猜想 在本题中上式可以取等号。并且不难发现:当 n5n\leq 5 时,扇区中可以填的最大数为 ii;当 n>5n>5 时,扇区中可填最大数为 22。所以只需爆搜出每一位即可。

hzwer7629 | 小奇挖矿 2

Portal

对于 60% 的数据,可以直接写出状态转移方程:
fi=max{fi4,fi7}+aif_i=\max {f_{i-4},f_{i-7}} +a_i

然后当成普通的一维 DP 做可以拿下 60pts。

对于 100% 的数据,由于 m109m\leq 10^9 如果直接用数组记录每个点的收益显然会 MLE。