给出N*M矩阵。每一个点建立灯塔有花费。每一个点的灯塔有连接范围，求每一行都建立一个灯塔的最小花费，要求每相邻两行的灯塔能够互相连接。满足 |j-k|≤f(i,j)+f(i+1,k)

DP思路，dp[i][j]=在第i行的j位置放置灯塔的最小花费。dp[i][j]=Min(dp[i-1][k]+a[i][j]),同一时候更新当前点能够覆盖该行的全部位置的最小值

要求上个区间的最小值，用线段树优化，否则超时

滚动数组，否则超内存

#include "stdio.h"

#include "string.h"

int inf=0x3f3f3f3f;

struct node

{

    int Max,Min,lazy; // min记录区间最小值。max记录区间的最小值的最大值

    short int l,r;

}data[2][20100];

int a[110][5010],b[110][5010];

int Min(int a,int b)

{

    if (a<b) return a;

    else return b;

}

void Pushdown(int w,int k)

{

    if (data[w][k].l==data[w][k].r) return ;

    if (data[w][k].lazy==-1) return ;

    if (data[w][k].lazy<data[w][k*2].Min)

        data[w][k*2].Min=data[w][k*2].lazy=data[w][k].lazy;

    if (data[w][k].lazy<data[w][k*2+1].Min)

        data[w][k*2+1].Min=data[w][k*2+1].lazy=data[w][k].lazy;

    data[w][k].lazy=-1;

}

void build(int w,int l,int r,int k)

{

    int mid;

    data[w][k].l=l;

    data[w][k].r=r;

    data[w][k].lazy=-1;

    data[w][k].Min=inf;

    data[w][k].Max=inf;

    if (l==r) return ;

    mid=(l+r)/2;

    build(w,l,mid,k*2);

    build(w,mid+1,r,k*2+1);

}

void updata(int w,int l,int r,int k,int op)

{

    int mid;

    if (data[w][k].l==data[w][k].r)

    {

        if (data[w][k].Min>op) data[w][k].Max=data[w][k].Min=op;

        return ;

    }

    if (data[w][k].l==l && data[w][k].r==r )

    {

        mid=(data[w][k].l+data[w][k].r)/2;

        if (op<data[w][k].Max) // 若以下区间存在最小值>op,则继续向下更新

        {

            updata(w,l,mid,k*2,op);

            updata(w,mid+1,r,k*2+1,op);

            data[w][k].Max=op;

        }

        if (op<data[w][k].Min)

            data[w][k].Min=data[w][k].lazy=data[w][k].Max=op;

        return ;

    }

    Pushdown(w,k);

    mid=(data[w][k].l+data[w][k].r)/2;

    if (r<=mid) updata(w,l,r,k*2,op);

    else

        if (l>mid) updata(w,l,r,k*2+1,op);

    else

    {

        updata(w,l,mid,k*2,op);

        updata(w,mid+1,r,k*2+1,op);

    }

    data[w][k].Min=Min(data[w][k*2].Min,data[w][k*2+1].Min);

}

int query(int w,int l,int r,int k)

{

    int mid;

    if (data[w][k].l==l && data[w][k].r==r)

        return data[w][k].Min;

    Pushdown(w,k);

    mid=(data[w][k].l+data[w][k].r)/2;

    if (r<=mid) return query(w,l,r,k*2);

    else

        if (l>mid) return query(w,l,r,k*2+1);

    else

        return Min(query(w,l,mid,k*2),query(w,mid+1,r,k*2+1));

}

void pri(int w,int k)

{

    if (data[w][k].l==data[w][k].r)

    {

        printf("%d ",data[w][k].Min);

        return ;

    }

    Pushdown(w,k);

    pri(w,k*2);

    pri(w,k*2+1);

}

int main()

{

    int n,m,i,j,l,r,x;

    while (scanf("%d%d",&n,&m)!=EOF)

    {

        if (n==0 && m==0) break;

        for (i=1;i<=n;i++)

            for (j=1;j<=m;j++)

            scanf("%d",&a[i][j]);

        for (i=1;i<=n;i++)

            for (j=1;j<=m;j++)

            scanf("%d",&b[i][j]);

        build(1,1,m,1);

        for (i=1;i<=m;i++)

        {

            l=i-b[1][i]; if (l<1) l=1;

            r=i+b[1][i]; if (r>m) r=m;

            updata(1,l,r,1,a[1][i]); // 初始化第一行每个位置的最优值

        }

        for (i=2;i<=n;i++)

        {

            build(i%2,1,m,1);

            for (j=1;j<=m;j++)

            {

                l=j-b[i][j]; if (l<1) l=1;

                r=j+b[i][j]; if (r>m) r=m;

                x=query(1-i%2,l,r,1); //　对于每一行的每个位置。查找上一行能够连接到该位置的最小值

                updata(i%2,l,r,1,x+a[i][j]);  // 更新该行该位置能够覆盖到的全部位置的最小值

            }

        }

       /* for (i=1;i<=n;i++)

        {

            printf("\n\n");

            pri(i,1);

        }

        printf("\n");*/ //debug

        printf("%d\n",data[n%2][1].Min);

    }

    return 0;

}