简单介绍

• 数字三角形这东西，出现了有一定的年头了。于是，出现了一些变种……

眼下已知的题目

• 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<stdio.h>
#define maxint 2000000000
#define min(a,b) (a<b?
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版的。是不变的。