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

雨点打透心脏的1/2处 2024-03-26 16:07 59阅读 0赞

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

[4550. 超级跳跳跳 - AcWing题库][4550. _ - AcWing]

题意：

![b1847ff69760b8fd8560f99303beec28.png][]

思路：

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

因此就是个很典的前后缀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;
    }

[4550. _ - AcWing]: https://www.acwing.com/problem/content/4553/
[b1847ff69760b8fd8560f99303beec28.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/5905f4b5bdcc49b98492ab4cca1d230d.png