ヤクザ:縄張りを奪う-C++
21062 ワード
畑を掘る
コード#コード#
[トレースバックコード]-タイムアウト
#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;
}
[トレースバックコード]-タイムアウト
#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;
}
:DPのコア
메모제이션(memoization)
Reference
この問題について(ヤクザ:縄張りを奪う-C++), 我々は、より多くの情報をここで見つけました https://velog.io/@neity16/Programers-땅따먹기-Cテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol