晴天小猪历险记之 Hill
【背景 Background】
在很久很久以前，有一个动物村庄，那里是猪的乐园（^_^），村民们勤劳、勇敢、善良、团结……
不过有一天，最小的小小猪生病了，而这种病是极其罕见的，因此大家都没有储存这种药物。所以晴天小猪自告奋勇，要去采取这种药草。于是，晴天小猪的传奇故事便由此展开……
【描述 Description】
这一天，他来到了一座深山的山脚下，因为只有这座深山中的一位隐者才知道这种药草的所在。但是上山的路错综复杂，由于小小猪的病情，晴天小猪想找一条需时最少的路到达山顶，但现在它一头雾水，所以向你求助。
山用一个三角形表示，从山顶依次向下有1段、2段、3段等山路，每一段用一个数字T（1<=T<=100）表示，代表晴天小猪在这一段山路上需要爬的时间，每一次它都可以朝左、右、左上、右上四个方向走（**注意**：在任意一层的第一段也可以走到本层的最后一段或上一层的最后一段）。
晴天小猪从山的左下角出发，目的地为山顶，即隐者的小屋。
【输入格式 Input Format】
第一行有一个数n（2<=n<=1000），表示山的高度。
从第二行至第n+1行，第i+1行有i个数，每个数表示晴天小猪在这一段山路上需要爬的时间。
【输出格式 Output Format】
一个数，即晴天小猪所需要的最短时间。
【样例输入 Sample Input】
5
1
2 3
4 5 6
10 1 7 8
1 1 4 5 6
【样例输出 Sample Output】
10
【时间限制 Time Limitation】
各个测试点1s
【题解 Solution】
题目里说：在任意一层的第一段也可以走到本层的最后一段或上一层的最后一段。我们需要加上一句：反之亦然；这样就可以做了。
这是挺有意思的一题。对我这样的初学者来说，也是不算水题了。这题的原型来自经典的数字三角形，但是条件有所修改。题目简要描述如下：
给出一个N行数字三角形，其中第i行有i列。记i行j列的数字为(i,j)，则求从(1,N)到(1,1)的一条路径，要求路径上的数字之和最小。移动规则为：到达(i,j)位置时只能向左、右、左上、右上四个方向移动。特殊地，三角形左右互通，即由(i,1)可移动到(i,i)或(i-1,i-1)；(i,i)同理。
的确和经典的数字三角形很像吧，仅仅在移动规则上加了两条：1.允许同行的左右移动；2.左右互通。但是加上这小小的两个条件，题目就大不一样了。
下面是三种方法，但事实上前两种都是扯淡，是我在思考时得到的不可行方法。建议直接跳到第三条分割线之后。
注：各转移方程都没有把行两端情况单另写出来……
———————————第1条分割线凌空飞过—————————————
既然和经典问题这么像，那我们就先按照经典的方程来做吧。在经典方程上简单加上向左、向右两个决策，这样行不行呢？显然，现在出现了两种环，一种是向一个方向走再折回来，一种是一直走到行首或行末，然后绕一个大圈回来。这两种环的存在导致了后效性的产生。当然，这时候递归下降还是可行的（用一个bool数组记录哪些点已经到达），但是复杂度无疑是巨大的指数级。我就这么交了一次，结果一个点都没过……-_-
———————————第2条分割线凌空飞过—————————————
这样改动后真的失去无后效性了么？引起这一变化的原因就是同行内的移动，那我们就从同行内的移动考虑。在同行内移动时，一定是从左或从右直接移动到某一个点，然后向上移；绝对不会在一行里面走回头路，也不会赖在一行里不走的。这样，行间转移的无后效性就很明显了。若用dp(i,j)表示(i,j)到(1,1)的路径最小权和，sum(i,j,k)表示第i行中j列到k列的路径最小权和，很容易写出下面的方程：
dp(i,j)=min{ sum(i,j,k)+min{dp(i-1,j),dp(i-1,j-1)} } (1<=k<=i)
其中，sum(i,j,k)可以在O(1)时间内获得。DP的子问题数是O(N^2)的，转移是O(N)的，这样复杂度就是O(N^3)的，对N<=1000这个数据规模还是太大了。至于能得多少分，由于我没写，就不知道了。
———————————第3条分割线凌空飞过—————————————
事实上我们可以利用同行内的递推关系来获得O(N^2)的算法。我们把在第一条分割线下被否定的方程写出来：
dp(i,j)=min{ min{dp(i-1,j),dp(i-1,j)},dp(i,j-1),dp(i,j+1) }+num(i,j)
其中num(i,j)即为位置(i,j)上的数。即对于一个点(i,j)，或者上移至前一行，或者在本行内向左或向右移动。由于不走回头路，若一个点(i,j)的dp值由左边的点(i,j-1)转移得到，则(i,j-1)也必由它自己的左边的点(i,j-2)或前一行转移得到而不必考虑向右。即：
若dp(i,j)=dp(i,j-1)+num(i,j)
则必有dp(i,j-1)=min{ dp(i,j-2),min{dp(i-1,j-2),dp(i-1,j-1)} }+num(i,j-1)（不必考虑转移到dp(i,j)）
向右转移时也是同理。
现需找一个行内递推的起点。我们可取此行内min{dp(i-1,j),dp(i-1,j-1)}+num(i,j)最小的一点，因为它的dp值只能由上一行转移得到。以此为起点，向左向右分别推一圈，就得到了整行内的dp值。
就写这么多……感觉越写越乱了……还是看代码吧：
/*
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;
}
可能你对下面的文章也感兴趣：
