Vacation

Vacation

Atcoder easy

لديك ثلاث مصفوفات \(a\)، \(b\)، و \(c\) من الأعداد الصحيحة، كل منها بطول \(N\). في كل موقع \(i\) (حيث \(0 \le i < N\)) يجب اختيار عنصر من \(a_i\)، \(b_i\)، أو \(c_i\).

شرط: لكل موقع \(i\) (حيث \(0 \le i < N - 1\))، يجب أن تأتي العناصر المختارة عند المواقع \(i\) و \(i + 1\) من مصفوفات مختلفة.

حدد واطبع أكبر مجموع للعناصر المختارة يمكن تحقيقه تحت هذا الشرط.

Noteملحوظة

لتبسيط المشكلة، سنمثل المصفوفات الثلاث \(a\)، \(b\)، و \(c\) كمصفوفة ثنائية الأبعاد واحدة \(d\) بأبعاد \(N \times 3\).
البعد الأول طوله \(N\)، والبُعد الثاني طوله \(3\)، حيث \(d_i\) هو مصفوفة تحتوي القيم [\(a_i\), \(b_i\), \(c_i\)].

Solution

سنحل هذه المشكلة باستخدام البرمجة الديناميكية.

دعنا نعرف الحالة:

\(f(i, type)\) هو أكبر مجموع ممكن إذا اعتبرنا أول \(i\) عنصر وعند الموقع \(i\) اخترنا \(d[i][type]\).

بعد ذلك نعرف الانتقال. هناك ثلاث انتقالات مختلفة بناءً على \(type\):

\(f(i , 0) = max(f(i - 1, 1) , f(i - 1, 2)) + d_{i,0}\)
\(f(i , 1) = max(f(i - 1, 0) , f(i - 1, 2)) + d_{i,1}\)
\(f(i , 2) = max(f(i - 1, 0) , f(i - 1, 1)) + d_{i,2}\)

الحالة الأساسية:

\(f(0, type) = d_{0,type}\)

تعقيد المساحة يحدده عدد الحالات، وهو \(O(N)\).

التعقيد الزمني هو عدد الحالات \(N\) مضروبًا في تعقيد كل انتقال \(O(1)\)، لذا التعقيد الكلي هو \(O(N)\).

#include <iostream>
using namespace std;

int dp[200000][3];
int d[200000][3];


int f (int i, int type) {
  
    if (i == 0) {
        return d[i][type];
    }

    if (dp[i][type] != -1) {
        return dp[i][type];
    }

  if(type == 0){
    dp[i][type] = max(f(i - 1, 1), f(i - 1, 2)) + d[i][type];
  }
  else if(type == 1){
    dp[i][type] = max(f(i - 1, 0), f(i - 1, 2)) + d[i][type];
  }
  else if(type == 2){
    dp[i][type] = max(f(i - 1, 0), f(i - 1, 1)) + d[i][type];
  }

    return dp[i][type];
}


int main() {
  
    for (int i = 0; i < 200000; i++) {
    for (int j = 0; j < 3; j++) {
          dp[i][j] = -1;
    }
    }

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
    for (int j = 0; j < 3; j++) {
      cin >> d[i][j];
    }
    }

    cout << max(max(f(n - 1, 0), f(n - 1, 1)), f(n - 1, 2)) << "\n";
}