cafelier@SRM

TCO12 Round2A 450

04:04 |

300に泥はまりしすぎて時間かけられなかったせいで焦りすぎて変なtypoを直せず…終了直前にサンプル通せたコードがそのままpractice通ったので無念です。以下ちょっと整理したもの

template<typename T>
struct DP3
{
   int N1, N2, N3;
   vector<T> data;
   DP3(int N1, int N2, int N3, const T& t = T())
      : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); }
   T& operator()(int i1, int i2, int i3)
      { return data[ ((i1*N2)+i2)*N3+i3 ]; }
   void swap(DP3& rhs)
      { data.swap(rhs.data); }
};

class CucumberWatering { public:
   long long theMin(vector <int> x, int K)
   {
      const int N = x.size();

      vector<pair<LL,int> > pts;
      for(int i=0; i<N; ++i)
         pts.push_back(make_pair(x[i], i));
      sort(pts.begin(), pts.end());

      DP3<LL> dp(N, K+1, N, -12345678987654321LL);
      dp(0, 0, 0) = dp(0, 1, 0) = 0;
      for(int i=1; i<N; ++i)
         for(int warpUsed=0; warpUsed<=K; ++warpUsed) {
            for(int lastWarpPt=0; lastWarpPt<i; ++lastWarpPt)
               dp(i,warpUsed,lastWarpPt) = dp(i-1,warpUsed,lastWarpPt);

            LL maxGain = 0;
            if( warpUsed > 1 )
               for(int p=0; p<i; ++p) {
                  LL gain = 0;
                  LL P = pts[p].first;
                  LL Q = pts[i].first;
                  for(int k=1; k<N; ++k) {
                     LL X = min(x[k-1], x[k]);
                     LL Y = max(x[k-1], x[k]);
                     gain += max(0LL, (Y-X) - (abs(X-P) + abs(Y-Q)));
                  }
                  maxGain = max(maxGain, dp(i,warpUsed-1,p) + gain);
               }
            dp(i,warpUsed,i) = maxGain;
         }

      LL naive = 0;
      for(int i=1; i<N; ++i)
         naive += abs(LL(x[i-1]) - LL(x[i]));

      LL maxGain = 0;
      for(int w=0; w<=K; ++w)
         for(int p=0; p<N; ++p)
            maxGain = max(maxGain, dp(N-1,w,p));

      return naive - maxGain;
   }
};

x座標でソートして、あとは各点で、「ここにワープポイント置いたらいくら距離を稼げるか」の最大値を求める感じで。稼げる分の距離はすぐ左のワープゾーンがわかればわかる（何個もワープゾーンを跨ぐワープの分の稼ぎは区間毎にわけて集計される）。