Information
- ID
- 990
- Time
- 1000ms
- Memory
- 16MiB
- Difficulty
- 4
- Tags
- # Submissions
- 60
- Accepted
- 28
- Uploaded By
用 dp[i] 表示从前 i 个数中任取出若干个数(不能取相邻的数)的最大值
对于第 i 个数,可以取也可以不取,如果取则 dp[i]=dp[i-2]+a[i] ,不取则 dp[i]=dp[i-1],从二者中取最大值
所以递推公式 dp[i]=max(dp[i-2]+a[i],dp[i-1])
递推初始值为 dp[1]=a[i]
#include<bits/stdc++.h>
using namespace std;
#define ioio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define debug(x) cout<<#x<<":"<<x<<endl;
#define L(k) k<<1
#define R(k) k<<1|1
#define P pair
#define P1 first
#define P2 second
#define u_map unordered_map
#define p_queue priority_queue
typedef long ll;
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int INF2 = (1 << 31);
const int N = 1e2 + 7;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
/*-------------------------------------------------*/
int n;
int a[N];
int dp[N];
int main(){
ioio
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
dp[1]=a[1];
for(int i=2;i<=n;i++)
dp[i]=max(dp[i-2]+a[i],dp[i-1]);
cout<<dp[n]<<endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define accelerate ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl "\n";
#define mod 12345
#define ll long long
#define PII pair<int,int>
#define INF 0x3f3f3f3f
const int N=1e2+10;
ll n,m,k,x,y,T;
ll a[N];
ll pre[N][2];
int main(){
accelerate;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
pre[i][0]+=max(pre[i-1][1],pre[i-1][0]);
pre[i][1]+=pre[i-1][0]+a[i];
}
cout<<max(pre[n][0],pre[n][1]);
return 0;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.