[伯俊/C+]14889号開始とリンク

最近忙しくて、白俊をまともにアップロードできませんでした.
気を取り直したいのですが、課題が多すぎて、もうすぐ中間試験です.
でも最善を尽くして解決します!
問題は次のとおりです.
この問題は、三星(サムスン)のソフトウェア機能がテストされた問題だ.


問題のポイントは次のとおりです.⭐️
1.2つのグループに分ける(分割)
2.各グループの能力値を求める
💡まず、入力を2 D配列に保存します.
💡dfsを使用して2つのグループに分割します.
(2組の情報は配列resとベクトルtmpにそれぞれ置かれる.)
💡次に、デュアルfor文で各グループのコンピテンシー値を計算し、変数gapにより小さな値を更新し続けます.
最初に作成された完全なコードは次のとおりです.

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

int n;
int res[21]={0, };
int a[20][20]={0, };
vector<int> v;

int total = 0;
int gap = INT_MAX;

void dfs(int cnt){
    if(cnt==n/2 + 1){
        vector<int> tmp = v;
        for(int i=1; i<=n/2; i++){
            tmp.erase(remove(tmp.begin(), tmp.end(), res[i]), tmp.end()); // 원소 지우기
        }

        int sum = 0, sum2 = 0;

        for(int i=1; i<=n/2; i++){
            for(int j=1; j<=n/2; j++){
                sum += a[res[i]][res[j]]; // 그룹1 능력치
                sum2 += a[tmp[i-1]][tmp[j-1]]; // 그룹2 능력치
            }
        }
        
        // 최솟값 갱신시키기
        gap = min(gap, abs(sum-sum2));
    }
    else{
        for(int i=res[cnt-1]+1; i<n; i++){
            res[cnt]=i;
            dfs(cnt+1);
            res[cnt]=0;
        }
    }
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  cin>>n;
  for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
          cin>>a[i][j]; // 2차원 배열 입력받기
          total += a[i][j];
      }
      v.emplace_back(i);
  }
  res[0]=-1;
  dfs(1);

  cout<<gap<<"\n";
  return 0;
}

このコードは、すべての分割プロセスを実行します.
しかし、分割の過程は半分しか実行できないと思いました.
0、1、2、3または
2、3/0と1の分割は同じですから.
したがって、時間を短縮するために、いくつかの要素を1つのグループに固定します.

  res[1]=0;
  dfs(2);

この改善された最終プールは次のとおりです.🙆🏻‍♀️

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

int n;
int res[21]={0, };
int a[20][20]={0, };
vector<int> v;

int total = 0;
int gap = INT_MAX;

void dfs(int cnt){
    if(cnt==n/2 + 1){
        vector<int> tmp = v;
        for(int i=1; i<=n/2; i++){
            tmp.erase(remove(tmp.begin(), tmp.end(), res[i]), tmp.end()); // 원소 지우기
        }

        int sum = 0, sum2 = 0;

        for(int i=1; i<=n/2; i++){
            for(int j=1; j<=n/2; j++){
                sum += a[res[i]][res[j]]; // 그룹1 능력치
                sum2 += a[tmp[i-1]][tmp[j-1]]; // 그룹2 능력치
            }
        }
        
        // 최솟값 갱신시키기
        gap = min(gap, abs(sum-sum2));
    }
    else{
        for(int i=res[cnt-1]+1; i<n; i++){
            res[cnt]=i;
            dfs(cnt+1);
            res[cnt]=0;
        }
    }
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  cin>>n;
  for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
          cin>>a[i][j]; // 2차원 배열 입력받기
          total += a[i][j];
      }
      v.emplace_back(i);
  }
  res[1]=0; // 그룹에 특정 멤버 고정시키기 -> 1/2로 분할 줄이기
  dfs(2);

  cout<<gap<<"\n";
  return 0;
}

実際、私たちは時間をチェックしました.

60ms -> 32ms
本当に半分减っているのが见えます.⌝