<= 求赞qwq,码字不易,你的支持是我写作的动力
宣传一下算法提高课题解合集
1049.大盗阿福
阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 $N$ 家店铺,每家店中都有一些现金。
阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。
作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。
他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金?
输入格式
输入的第一行是一个整数 $T$,表示一共有 $T$ 组数据。
接下来的每组数据,第一行是一个整数 $N$ ,表示一共有 $N$ 家店铺。
第二行是 $N$ 个被空格分开的正整数,表示每一家店铺中的现金数量。
每家店铺中的现金数量均不超过1000。
输出格式
对于每组数据,输出一行。
该行包含一个整数,表示阿福在不惊动警察的情况下可以得到的现金数量。
数据范围
$1 \le T \le 50$,
$1 \le N \le 10^5$
输入样例
2
3
1 8 2
4
10 7 6 14
输出样例
8
24
算法1
(DP) $O(n)$
观察题目:
每一家店铺只可能有两种状态:洗劫或没被洗劫
容易想到三种经典思路:
1.枚举:容易看出,复杂度是指数级,放弃
2.贪心:洗劫商店的个数和答案没有强关联
3.dp:没有区间,考虑线性dp
线性dp模板:(以i结尾) f[i] = 1 ~ i 的答案
本体模板:f[i] = 1 ~ i 的商店洗劫后获得的金币最大值
本体正解: 考虑“以i结尾”,状态应该分为两种情况:
$f_{i, 0}$ 表示不洗劫商店i的最大值
$f_{i, 1}$ 表示洗劫商店i的最大值
$$ f_{i, 0} = \max\Big( f_{i - 1, 1}, f_{i-1, 0} \Big) $$
$$ f_{i, 1} = f_{i-1, 0} + w_i $$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100009;
ll n, T;
ll x[N], f[N][2];
void solve()
{
cin >> n;
for(int i = 1;i <= n;++ i) cin >> x[i];
for(int i = 1;i <= n + 1;++ i)
{
f[i][1] = f[i - 1][0] + x[i];
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
}
cout << f[n + 1][0] << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while(T --) solve();
return 0;
}
将代码缩短后:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100009;
ll n, T;
ll x[N], f[N][2];
void solve()
{
cin >> n;
for(int i = 1, x;i <= n + 1;++ i)
{
if(i <= n) cin >> x;
f[i][1] = f[i - 1][0] + x;
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
}
cout << f[n + 1][0] << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while(T --) solve();
return 0;
}
算法2
(dp + 滚动数组) $O(n^2)$
blablabla 用滚动数组优化
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100009;
ll n, T;
ll x[N], f[3][3];
void solve()
{
cin >> n;
f[0][1] = f[0][0] = 0;//记得初始化~
for(int i = 1, x;i <= n + 1;++ i)
{
if(i <= n) cin >> x;
f[i & 1][1] = f[(i - 1) & 1][0] + x;
f[i & 1][0] = max(f[(i - 1) & 1][0], f[(i - 1) & 1][1]);
}
cout << f[(n + 1) & 1][0] << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while(T --) solve();
return 0;
}