标签：魅力值 int 蓝桥 101 线性 include dp
蓝桥云课-最大魅力值
#include <iostream>
#include <cstring>
using namespace std;
int a[101];
int dp[101][101];
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
memset(dp, -10000, sizeof(dp)); // 避免被非法状态影响
dp[0][0] = 0;
dp[1][0] = 0;
dp[1][1] = a[1];
for(int i = 2; i <= n; ++i) {
dp[i][0] = 0;
for(int j = 1; j <= n; ++j) {
dp[i][j] = max(dp[i - 2][j - 1] + a[i], dp[i - 1][j]);
}
}
cout << dp[n][n/2] << endl;
return 0;
}
// dp[i][j]: 到了第i个景点, 选了j个景点的最大值
// dp[i][j] = max(dp[i - 2][j - 1] + a[i], dp[i - 1][j]) 因为不能选相邻的，所以要么选第i-2个加上现在的a[i]
// 要么选第i-1,选了i-1就不能选i，所以不用加a[i],二者取max
标签：魅力值,
int,
蓝桥,
101,
线性,
include,
dp
From： https://blog.csdn.net/BigNbYQQ/article/details/140245822