背包
解题思路
代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int w[N], f[N];
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];
f[1] = w[1];
for (int i = 2; i <= n; i++) {
f[i] = max(f[i - 2] + w[i], f[i - 1]);
}
cout << f[n] << endl;;
}
return 0;
}
状态机
解题思路
代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int w[N], f[N][2];
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];
for (int i = 1; i <= n; i++) {
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = f[i - 1][0] + w[i];
}
cout << max(f[n][0], f[n][1]) << endl;;
}
return 0;
}
兄弟有时间填个邀请码hhhhhhhhh(可以得AC币,邀请码在学生认证那填) 我的邀请码是:GUDFH