[ZeroJudge] e201: 期末打掃

題目連結:https://zerojudge.tw/ShowProblem?problemid=e201
稀有的過來寫個解。大學生活好累,每天都在被作業QAQ
一開始看錯題目了,不過因為沒看錯太多所以改個幾行就過了XD
看到這題我的第一個想法是樹DP,所以想說先想想看有沒有甚麼有用的性質。感受了一下發現我可以定義$f_u(x)$代表在$x$時間點進入$u$後再出來的時間點,那可以發現$f_u(x)=\max(a_{u0},x+d_u)$,其中$d_u$代表可以不用等待就都檢查完$u$的子樹的時間,$a_{u0}$代表如果是第0個時間點就從$u$出發那要多久後才能回到$u$並把所有教室都檢查完的時間。證明這部分成立的方法也很簡單(不過我很笨想了很久QAQ),假設在時間點$t\geq 0$,存在一種走法最佳,那我們可以知道他的時間一定$\geq t+d_u$,因為不管怎樣我們至少一定要把底下整棵子樹都走過一遍才能回來,另外我們也知道那個最佳走法的時間也$\geq a_{u0}$,因為如果他更小的話,我們在時間點$0$的時候就可以故意等到時間點$t$在走,這樣可以走出更加的解,與假設不合,這樣我們就證明了在任意時間點$t$的任意解$g$都有$g \geq f_u(t)$,而且明顯$f_u(t)$是可以達到的,因為我們可以照著$t=0$的路徑走,那如果中間很順利不用逗留的話就達到了$f_u(x)=x+d_u$,而若是要逗留的話,那在逗留的當下我們接著的時間就會跟$t=0$的時候同步了,所以這時$f_u(x)=a_{u0}$。
講了這麼多我們現在終於知道一個人在時間點$x$進入$u$後出來的時間,那接下來就是要決定當我們在$u$的時候該以怎樣的順序走訪他的子樹們$v$了,而這時我盯著$f_u(x)=\max(a_{u0},x+d_u)$的圖(一堆平移過後的ReLU函數w)一段時間後猜想順序就是按著$f_u$的轉折點的$x$座標由小到大拜訪就會是好的,也就是按照$a_{u0}-d_u$由小到大走訪就會是最佳的,不過這部分我證不太出來,所以後來就依靠Z3證明了對於任意$s,t,x_0\geq 0$都有$a_{s0} - d_s \leq a_{t0} - d_t \Rightarrow f_t(f_s(x_0)) \leq f_s(f_t(x_0))$,那我們就可以接著證如果存在一組最佳解,那我們交換他相鄰逆序的部分也不會比較差,所以透過照著$a_{u0}-d_u$排序的解一定只會跟最佳解一樣好。
以上,再稍微處理一下從子樹上來的時候的函數值,我們就可以開心$O(TN\log{N})$的做完這題了XD
p.s 話說有沒有人要教我證我用Z3證的那個式子QAQ
#include <bits/stdc++.h>
using namespace std;
using lld = int64_t;
const int N = 50000 + 5;

lld d[ N ];
vector< pair< int, lld > > G[ N ];

pair< lld, lld > dfs( int, int );

int main() {
 ios_base::sync_with_stdio( false );
 cin.tie( nullptr );
 int t; cin >> t;
 while ( t -- ) {
  int n; cin >> n;
  for ( int i = 2 ; i <= n ; ++ i )
   cin >> d[ i ];
  for ( int i = 2 ; i <= n ; ++ i ) {
   int u, v, w; cin >> u >> v >> w;
   G[ u ].emplace_back( v, w );
   G[ v ].emplace_back( u, w );
  }
  lld a, w; tie( a, w ) = dfs( 1, 1 );
  cout << max( a, w ) << '\n';
  for ( int i = 1 ; i <= n ; ++ i )
   G[ i ].clear();
 }
 return 0;
}

pair< lld, lld > dfs( int u, int f ) {
 vector< pair< lld, lld > > sub;
 lld y = 0, w = 0;
 for ( auto e : G[ u ] ) {
  if ( e.first == f ) continue;
  sub.push_back( dfs( e.first, u ) );
  sub.back().first += e.second;
  sub.back().second += e.second * 2;
  w += sub.back().second;
 }
 sort( sub.begin(), sub.end(), []( const pair< lld, lld >& a, const pair< lld, lld >& b ) {
  return a.first - a.second < b.first - b.second;
 } );
 for ( auto s : sub ) y = max( s.first, s.second + y );
 return { max( y, d[ u ] ), w };
}

留言

  1. We can create microstructures and course of thin, fragile components thanks to the fantastic accuracy of our CNC machines. If the Bottle Warmers drive system is weaker than the machine's structural integrity, then the drive system simply pushes in opposition to the obstruction, and the drive motors "slip in place". The machine software might not detect the collision or the slipping, so for example the software should now be at 210mm on the X-axis, however is, in reality, at 32mm where it hit the obstruction and stored slipping. All of the next software motions shall be off by −178mm on the X-axis, and all future motions are now are|are actually} invalid, which may end in further collisions with clamps, vises, or the machine itself. This is frequent in open-loop stepper systems however isn't attainable in closed-loop systems until mechanical slippage between the motor and drive mechanism has occurred. Precision machined components require proper execution, knowledge and a spotlight to detail.

    回覆刪除

張貼留言

這個網誌中的熱門文章

[IOICamp] 最小公倍數問題

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1209. 圖論 之 二分圖測試