[VIJOS 1006]晴天小猪历险记之 Hill

所谓的解题报告在这里：

http://blog.sina.com.cn/s/blog_4a443fd701000a7v.html

/*
  Name: Vijos P1006 晴天小猪历险记之Hill
  Author: 巨菜逆铭
  Date: 24-08-07 18:58
  Description: Dynamic Programming
*/

#include <iostream>
#include <fstream>
#include <cassert>
#define SYS sys\
tem
using namespace std;
unsigned long N,num[1001],dp[2][1002];
int main(){
        //The Amulet
        unsigned rp=unsigned(-1);

        //ifstream cin("input.txt");
        cin >> N >> dp[0][1];
        dp[0][0]=dp[0][2]=dp[0][1];
        bool flag=1;
        for(int i=2;i<=N;i++,flag=!flag){
                int m,m_num=INT_MAX;
                for(int j=1;j<=i;j++){
                        cin >> num[j];
                        dp[flag][j]=num[j]+min(dp[!flag][j],dp[!flag][j-1]);
                        if(m_num>dp[flag][j])        m=j,m_num=dp[flag][j];
                }
                //walk rightward
                for(int j=m+1;j<=i;j++)
                        if(dp[flag][j]>dp[flag][j-1]+num[j])
                                dp[flag][j]=dp[flag][j-1]+num[j];
                if(dp[flag][1]>dp[flag][i]+num[1])
                        dp[flag][1]=dp[flag][i]+num[1];
                for(int j=2;j<m;j++)
                        if(dp[flag][j]>dp[flag][j-1]+num[j])
                                dp[flag][j]=dp[flag][j-1]+num[j];
                //walk leftward
                for(int j=m-1;j>=1;j--)
                        if(dp[flag][j]>dp[flag][j+1]+num[j])
                                dp[flag][j]=dp[flag][j+1]+num[j];
                if(dp[flag][i]>dp[flag][1]+num[i])
                        dp[flag][i]=dp[flag][1]+num[i];
                for(int j=i-1;j>m;j--)
                        if(dp[flag][j]>dp[flag][j+1]+num[j])
                                dp[flag][j]=dp[flag][j+1]+num[j];
                //special step for convenience
                dp[flag][0]=dp[flag][i];
                dp[flag][i+1]=dp[flag][1];
        }
        cout << dp[!flag][1] << endl;
        //SYS("pause");
        return 0;
}