Почему моя проблема с 3 разделами не проходит данный тестовый пример? (Проблема с 3 разделами) - PullRequest
Новая
       67

Почему моя проблема с 3 разделами не проходит данный тестовый пример? (Проблема с 3 разделами)

0 голосов
/ 05 мая 2020

В отношении следующего: 3-ЧАСТНАЯ проблема

Не могли бы вы объяснить, почему в решении Р. Гурунга cpp мы начинаем наши l oop j и k от суммы? Что, если мы начнем наш l oop с 0?

Я немного изменил данное решение следующим образом: 

#include <vector>
#include <bits/stdc++.h>
using namespace std;


int partition3(vector<int> &A)
{
  int sum = accumulate(A.begin(), A.end(), 0);
  if (sum % 3 != 0)
  {
    return false;
  }
  int size = A.size();

  vector<vector<int>> dp(sum + 1, vector<int>(sum + 1, 0));
  //bool dp[sum+1][sum+1];
  dp[0][0] = true;

  // process the numbers one by one
  for (int i = 0; i < size; i++)
  {
    for (int j = 0; j <=2*(sum/3); j++)
    {
      for (int k = 0; k <=2*(sum/3); k++)
      {
        if (dp[j][k])
        {
          dp[j + A[i]][k] = true;
          dp[j][k + A[i]] = true;
        }
      }
    }
  }

  for(int i=0;i<=sum;i++)
  {
    for(int j=0;j<=sum;j++)
    {
      cout<<dp[i][j]<<" ";
    }
    cout<<'\n';
  }

  return dp[sum / 3][sum / 3];
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  vector<int> a;

  int n;
  cin>>n;

  for(int i=0;i<n;i++)
  {
    int input;
    cin>>input;
    a.push_back(input);
  }


  cout<<partition3(a);
}

My l oop в partition3 () работает почти для всех решения, и он даже прошел тестовые примеры судьи и казался правильным, за исключением случаев, когда я дал конкретный c тестовый пример: 

10
20 9 13 27 25 7 2 9 17 15

Для данного тестового примера ответ должен быть 0 Это должно ожидать программа для вывода 0. Поскольку каждый должен получить 48, а если кто-то возьмет 27, он не может получить 48, как бы он ни выбрал.

Но мой прежний алгоритм, а именно тот, кто передает программу, выдает 1 .

Кто-нибудь, пожалуйста, объясните ошибку? Я не понимаю, а также почему он проходит судью, когда он неправильный?

EDIT-1 

  for (int i = 0; i < size; i++)
  {
    for (int j = sum; j >=0; --j)
    {
      for (int k = sum; k >=0; --k)
      {
        if (dp[j][k])
        {
          dp[j + A[i]][k] = true;
          dp[j][k + A[i]] = true;
        }
      }
    }
  }

Вышеупомянутые циклы дают правильный ответ (0 ) к заданному тесту. Объясните, пожалуйста, ошибку в моем решении.

1 Ответ

0 голосов
/ 05 мая 2020

Предполагая, что функция Р. Гурунга верна. Между dp и A существует зависимость, поэтому вы не можете заполнить его от начала до конца, как вы предлагаете.

...