AcWing 1049. 大盗阿福
原题链接
简单
作者:
aqua_
,
2024-04-23 14:10:51
,
所有人可见
,
阅读 2
dfs
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int t, n;
int m[N];
int dfs(int x)
{
if(x > n) return 0;
return max(dfs(x + 1), dfs(x + 2) + m[x]);
}
int main()
{
cin >> t;
while(t -- )
{
cin >> n;
for(int i = 1; i <= n; i ++ )
cin >> m[i];
cout << dfs(1) << endl;
}
return 0;
}
记忆化搜索
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int t, n;
int m[N];
int memory[N]; //记忆化数组
int dfs(int x)
{
if(x > n) return 0;
if(memory[x]) return memory[x]; //记忆化搜索
memory[x + 1] = dfs(x + 1);
memory[x + 2] = dfs(x + 2) + m[x];
return max(memory[x + 1], memory[x + 2]);
}
int main()
{
cin >> t;
while(t -- )
{
cin >> n;
memset(memory, 0, sizeof memory);
for(int i = 1; i <= n; i ++ )
cin >> m[i];
cout << dfs(1) << endl;
}
return 0;
}
递推
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int t, n;
int m[N];
int f[N];
int main()
{
cin >> t;
while(t -- )
{
cin >> n;
memset(f, 0, sizeof f);
for(int i = 1; i <= n; i ++ )
cin >> m[i];
for(int i = n; i >= 1; i -- )
f[i] = max(f[i + 1], f[i + 2] + m[i]);
cout << f[1] << endl;
}
return 0;
}