51nod——2487小b和环

dp[ i ][ 0 ] : 第i个位置不取

dp[ i ][ 1 ] : 第i个位置取

这样就可以得到状态转移方程：

dp[i][0]=max(max(dp[i][0],dp[i-1][1]),dp[i-1][0]);//这位置不选则前面位置可选可不选

dp[i][1]=max(dp[i][1],dp[i-1][0]+a[i]); 这位置选则前面位置必不选

然鹅要保证1和n不能相邻嘛，所以就跑两边。一遍不选1，n可选可不选，一遍选1，n必不选。这三个情况取max。

 #include <bits/stdc++.h>

 using namespace std;

 #define maxn 50050

 int dp[maxn][],a[maxn];

 int main(){

     ios::sync_with_stdio();

     cin.tie(); cout.tie();

     int n; cin>>n;

     for(int i=;i<n;i++) cin>>a[i];

     //不选第一个

     dp[][]=,dp[][]=a[];

     for(int i=;i<n;i++){

         dp[i][]=max(max(dp[i][],dp[i-][]),dp[i-][]);

         dp[i][]=max(dp[i][],dp[i-][]+a[i]);

     }

     int ans=max(dp[n-][],dp[n-][]);

     //选第一个,第二个一定不选

     memset(dp,,sizeof(dp));

     dp[][]=dp[][]=a[];

     for(int i=;i<n;i++){

         dp[i][]=max(max(dp[i][],dp[i-][]),dp[i-][]);

         dp[i][]=max(dp[i][],dp[i-][]+a[i]);

     }

     ans=max(ans,dp[n-][]);

     cout<<ans<<endl;

     return ;

 }

巴特西

51nod——2487小b和环

最新文章

热门文章