p1006.cpp

vijos动态规划5题:P1002,P1006,P1011,P1014,P1025

#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;
}