ヤクザ:縄張りを奪う-C++


畑を掘る



コード#コード#


[トレースバックコード]-タイムアウト

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int ans,N;
vector<int> arr;
vector<vector<int>> val;
void func(int depth, int start, int prev)
{
    int tot=0;
    if(depth == N){
        for(int i=0;i<N;i++)
            tot += arr[i];
        ans=max(ans,tot);
    }else{
        for(int i=start;i<N;i++)
        {
            for(int j=0;j<4;j++)
            {
                if(prev == j) continue;
                arr[depth] = val[i][j];
                func(depth+1, i+1, j);
            }
        }
    }
}
int solution(vector<vector<int>> land)
{
    int answer = 0;
    N = land.size();
    arr.resize(N);
    val.resize(N);
    for(int i=0;i<N;i++)
        for(int j=0;j<4;j++)
            val[i].push_back(land[i][j]);
    func(0, 0, -1);
    answer = ans;
    return answer;
}
  • 問題
    :Nが大きすぎて、タイムアウト
  • [回答正解]-DP

    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    int d[100003][4];
    int solution(vector<vector<int>> land)
    {
        int answer = 0;int N = land.size();
        d[0][0] = land[0][0];d[0][1] = land[0][1];
        d[0][2] = land[0][2];d[0][3] = land[0][3];
        for(int i=1;i<N;i++)
        {
            d[i][0] = max(d[i-1][1], max(d[i-1][2], d[i-1][3])) + land[i][0];
            d[i][1] = max(d[i-1][0], max(d[i-1][2], d[i-1][3])) + land[i][1];
            d[i][2] = max(d[i-1][0], max(d[i-1][1], d[i-1][3])) + land[i][2];
            d[i][3] = max(d[i-1][0], max(d[i-1][1], d[i-1][2])) + land[i][3];
        }
        answer = max(d[N-1][0], max(d[N-1][1], max(d[N-1][2], d[N-1][3])));
        return answer;
    }
  • key point!
    :DPのコア메모제이션(memoization)
  • を使用すること