北京网站设计公司有哪些,有几家做网站的公司,oa网站模板,网站制作与维护公司虽然只有1道题#xff0c;但是含金量还是够够di 文章目录题目题解代码实现题目 题解
我们直接对答案输出格式进行处理#xff1a;设第 iii 天走的路程为 aia_iai#xff0c;总路程为 S∑i1nleniS\sum_{i1}^nlen_iS∑i1nleni#xff0c;那么 v∑i1m(ai−Sm)2mv∑_{i1…虽然只有1道题但是含金量还是够够di 文章目录题目题解代码实现题目 题解
我们直接对答案输出格式进行处理设第 iii 天走的路程为 aia_iai总路程为 S∑i1nleniS\sum_{i1}^nlen_iS∑i1nleni那么 v∑i1m(ai−Sm)2mv∑_{i1}^m\frac{(a_i-\frac{S}{m})^2}{m}v∑i1mm(ai−mS)2
因为输出要乘以m2m^2m2就变成了 ∑i1m(ai−Sm)2∗m∑_{i1}^m(a_i-\frac{S}{m})^2*m∑i1m(ai−mS)2∗m
将求和 sigmasigmasigma 拆开得到 m∗(∑i1mai−∑i1m2∗ai∗Sm∑i1mS2m2)m*\Big(∑_{i1}^ma_i-\frac{∑_{i1}^m2*a_i*S}{m}∑_{i1}^m\frac{S^2}{m^2}\Big)m∗(∑i1mai−m∑i1m2∗ai∗S∑i1mm2S2)
再把 mmm 丢进去成为 m∗∑i1mai−∑i1m2∗ai∗S∑i1mS2mm*∑_{i1}^ma_i-∑_{i1}^m2*a_i*S∑_{i1}^m\frac{S^2}{m}m∗∑i1mai−∑i1m2∗ai∗S∑i1mmS2
上述式子就变了m∗∑i1mai−2∗S∗Sm∗S2mm*∑_{i1}^ma_i-2*S*Sm*\frac{S^2}{m}m∗∑i1mai−2∗S∗Sm∗mS2
化简得需要我们求 m∗∑i1mai2−S2m*∑_{i1}^ma_i^2-S^2m∗∑i1mai2−S2
因为 mmm 和 SSS 都是已知的要求出最小答案即需要我们求得 ∑i1mai2∑_{i1}^ma_i^2∑i1mai2 最小即可
我们要使得这个和最小可以设 dp[j][i]dp[j][i]dp[j][i] 表示 j 天走了 i 段路的最优方案
则有dp[j][i]min{dp[j−1][k](s[i]−s[k])2}(k∈[1i−1]dp[j][i]\min\Big\{dp[j-1][k](s[i]-s[k])^2\Big\}(k∈[1i-1]dp[j][i]min{dp[j−1][k](s[i]−s[k])2}(k∈[1i−1]其中 sis_isi 表示前 iii 段路的前缀和。
这样我们就可以直接对答案进行 DPDPDP时间复杂度为 O(nm2)O(nm^2)O(nm2)
但是很显然这样是不能把分拿满的。考虑优化。
对于这个式子很显然它的第一维是可以滚动的我们设 g(i)dp[j−1][i]g(i)dp[j-1][i]g(i)dp[j−1][i]
对于 iii 为 aaa 和 iii 为 bbb 两个点若 aaa 比 bbb 优则
g(a)(si−sa)2g(b)(si−sb)2g(a)(s_i-s_a)^2 g(b)(s_i-s_b)^2g(a)(si−sa)2g(b)(si−sb)2
⇒g(a)sa2−2∗si∗sag(b)sb2−2∗si∗sb\Rightarrow g(a)s_a^2-2*s_i*s_a g(b)s_b^2-2*s_i*s_b⇒g(a)sa2−2∗si∗sag(b)sb2−2∗si∗sb
⇒(g(a)sa2)−(g(b)sb2)sa−sb2∗si\Rightarrow \frac{(g(a)s_a^2)-(g(b)s_b^2)}{s_a-s_b}2*s_i⇒sa−sb(g(a)sa2)−(g(b)sb2)2∗si 【这一步成立的前提是因为 sss 是单调的】
可以发现左边是一个斜率式子。
斜率优化 dpdpdp 即可。
代码实现
#include cstdio
#include cstring
#define MAXN 3005
int n, m, len;
int dp[MAXN][MAXN];
int s[MAXN], deq[MAXN * MAXN];int Find_y ( int u, int v, int j ) {int first dp[j - 1][u] s[u] * s[u];int second dp[j - 1][v] s[v] * s[v];return first - second;
}
int Find_x ( int u, int v ) {return s[u] - s[v];
}int main() {scanf ( %d %d, n, m );for ( int i 1;i n;i ) {scanf ( %d, len );s[i] s[i - 1] len;}for ( int i 1;i n;i )dp[1][i] s[i] * s[i];for ( int j 2;j m;j ) {int head 1, tail 0;for ( int i 1;i n;i ) {while ( head tail Find_y ( deq[head], deq[head 1], j ) 2 * s[i] * Find_x ( deq[head], deq[head 1] ) )head ;dp[j][i] dp[j - 1][deq[head]] s[i] * s[i] - 2 * s[i] * s[deq[head]] s[deq[head]] * s[deq[head]];while ( head tail Find_y ( deq[tail], deq[tail - 1], j ) * Find_x ( i, deq[tail] ) Find_y ( i, deq[tail], j ) * Find_x ( deq[tail], deq[tail - 1] ) )tail --;deq[ tail] i;}}printf ( %d, m * dp[m][n] - s[n] * s[n] );return 0;
}
