【前后缀DP】Kuangbin 超级跳跳跳

【前后缀DP】Kuangbin 超级跳跳跳

10分钟速切，感觉已经掌握这种DP了，嘻嘻

4550. 超级跳跳跳 - AcWing题库

题意：

思路：

因为我们跳的那个点其实是路径的中间点，因此我们需要知道从开始到该点+从该点到结束的最短路径

因此就是个很典的前后缀DP

dp[i]表示从开始到该点的最短距离

dp2[i]表示从该点到结束的最短距离

然后就可以转移了，类似于最长上升子序列

Code：

#include <bits/stdc++.h>
#include <cmath>
#define int long long
using namespace std;
using i64 = long long;
const int mxn=1e3+10;
const int mxe=1e6+10;int n;
int a[mxn];
int dp[mxn],dp2[mxn];
void solve(){while(cin>>n&&n!=0){a[0]=0,a[n+1]=0;memset(dp,0,sizeof(dp));memset(dp2,0,sizeof(dp2));for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){for(int j=0;j<=i-1;j++){if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+a[i]);}}for(int i=n;i>=1;i--){for(int j=i+1;j<=n+1;j++){if(a[i]<a[j]) dp2[i]=max(dp2[i],dp2[j]+a[i]);}}int ans=0;for(int i=1;i<=n;i++){ans=max(ans,dp[i]+dp2[i]);}cout<<ans<<'n';}
}
void init(){}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;//cin>>__;init();while(__--)solve();return 0;
}