简单介绍
- 数字三角形这东西，出现了有一定的年头了。于是，出现了一些变种……
眼下已知的题目
Codevs1220 数字三角形
- 这题是原版IOI1994啊……
- f[i][j]=a[i][j]+max(f[i-1][j],f[i-1][j-1])。
Codevs2193 数字三角形ww 和 Codevs2198 数字三角形www
- 改了。必须得经过一个点。而且2198是2193的数据规模上的加强版。
- 然而这并没有什么L用，仅仅需让必须经过的点的权值加上一个特别大的值，最后的结果再减去这个值即可了。
- 实际上，状态转移方程是没有变的。
Codevs2189 数字三角形w
- 又改了。这回让你最后的结果取模最大。
- 这回就不好办了，本来不小的一个数，加上那么一点点。再取模，可能就非常小了。显然这已经不再满足动态规划的无后效性原则了。
- 怎么办？
- 也非常好办，开一个布尔型的三维数组。记f[i][j][k]表示走到位置(i,j)时路径权值和再取模是否能得到k这个值，于是得到这样一个方程：f[i][j][k]=f[i][j][k] or f[i-1][j][(k-a[i][j]+m)%m] or f[i-1][j-1][(k-a[i][j]+m)%m]。这里面加上m是为了防止出现负下标。
最后找一遍那个目标状态存在即可了。
Vijos1006 晴天小猪历险记之Hill
- 好吧，个人感觉这题还是比較坑的，这回可就不是仅仅能光向左上或右上走了，而是还能够左右移动，而且从边界的一头还能够到达还有一头。
最关键的是，要从左下角走到山顶……
- 这回，又该怎么做呢？
- 先回归最原始的数字三角形的思路。在那个题目中，我们把爬到了哪一层做为阶段，由于某一点近由其左下和右下的的点推导而来，是满足无后效性原则的。但在这个题目中。无后效性原则被打破，由于每一层是个环。还能左右移动。
- 但实际上，这样的对后效性的影响是能够消除的。
由于由一个走过的点扩展而来的状态在决策时。是不可能再去选择这个点的。
这也就是说，左推仅仅能一直向左，右推仅仅能一直向右，也就是说。一个数的左右推值，仅仅会来自于它左右的两个数，显然左右推是不相互影响的。最后得到结果时。仅仅需将结果的四种来源取min，就能完毕任务。
当然，边界是须要特殊处理的。
- 详细的，在代码中有所解释。
- 好吧，个人感觉这题还是比較坑的，这回可就不是仅仅能光向左上或右上走了，而是还能够左右移动，而且从边界的一头还能够到达还有一头。
代码
个人认为。前三种不用给代码了，转移方程与思路都非常明白了……
于是，以下是Vijos1006的代码：
#include#define maxint 2000000000#define min(a,b) (a
a:b)
long a[1000][1000]={ 0}; long d[1000][1000]={ 0}; int main() { long n,i,j,k,tmp,x1,x2; scanf("%ld",&n); for(i=0;i<n;i++) for(j=0;j<=i;j++) scanf("%ld",&a[i][j]); for(i=0;i<n;i++) for(j=0;j<=i;j++) d[i][j]=maxint; for(i=0;i<n;i++) //对最后一行的处理 d[n-1][i]=a[n-1][i]; for(i=1;i<n;i++) d[n-1][i]=d[n-1][i-1]+a[n-1][i]; //由于最后一行右边的点仅仅能从左边的推来，所以有了这个预处理 for(i=n-1;i>=0;i--) d[n-1][i]=min(d[n-1][i],d[n-1][(i+1)%n]+a[n-1][i]); //往左走的话。肯定要先从左边翻过去再向左走 for(i=n-2;i>=0;i--) { d[i][0]=min(d[i+1][0],d[i+1][1]); //对左边界的处理 d[i][0]=min(d[i][0],d[i+1][i+1]); d[i][0]+=a[i][0]; d[i][i]=min(d[i+1][0],d[i+1][i]); //对右边界的处理 d[i][i]=min(d[i][i],d[i+1][i+1]); d[i][i]+=a[i][i]; for(j=1;j<=i-1;j++) //对中间位置的处理。这时候以下的一行已经处理完了 d[i][j]=min(d[i+1][j],d[i+1][j+1])+a[i][j]; d[i][0]=min(d[i][0],d[i][i]+a[i][0]); //左推与右推 for(j=1;j<=i;j++) d[i][j]=min(d[i][j],d[i][j-1]+a[i][j]); for(j=i;j>=0;j--) d[i][j]=min(d[i][j],d[i][(j+1)%(i+1)]+a[i][j]); } printf("%ld\n",d[0][0]); return 0; } 感慨
- 各个变种，层出不穷，但总之还都是棋盘型（坐标型）DP。
- 最主要的状态转移方程还是IOI1994版的。是不变的。
