POJ2353
穷逼DP时间复杂度O(n*m*m), 我想的就是这个..
牛逼DP时间复杂度O(n*m), 每一个room的状态都只能由左下右三个room决定, 从底向上双向递归..

POJ3612
把dp[i][h]分成两部分求解, 两部分可以分别以O(100)预处理, 求dp[i][h]是O(1), 所以整个复杂度只有O(n*100), 很棒
引用牛kevin0602的讲解(他的博客已经进不去了.. 不知为何)

先分h’大于h和小于h两种情况，这方程可写为f(n, h) = (H[i]-h)^2 + min { -C*h + min { f(n-1, h’)+C*h’ } (for h’ >= h),C*h + min { f(n-1, h’)-C*h’ } (for h’ < h) }，这样就把h’放在一起了，现在定义low(n, h) := min over h' >= h { f(n, h’)+C*h’ }，high(n, h) := min over h’ < h { f(n, h')-C*h' }，则可方程进一步写为f(n, h) = (H[i]-h)^2 + min { -C*h+low(n-1, h), C*h+high(n-1, h) }。在计算第n个电线杆的时候，low(n-1, h)和 high(n-1, h)用双重DP的方法可以在O(100)*3的时间内算出，则总时间复杂度为O(N*100)。

双向DP有点类似双向BFS, 两次BFS后可以O(1)求通过某点的入口-出口路径, 这两个题每一个状态都是可以表示成从两个状态比较来. 以后遇到类似的题目要警觉一下.. 或许还有三向之类的衍生..

代码:

2353

#include <stdio.h>

int main() {
    int M,N;
    scanf("%d%d",&N,&M);
    int dp[101][501];
    int path[101][501];   //0: down   1: left 2: right
    int a[101][501];

    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            scanf("%d",a[i]+j);

    for(int i=1;i<=M;i++) {
        dp[0][i]=0;
        path[0][i]=-1;
    }

    for(int i=1;i<=N;i++) {
        for(int j=1;j<=M;j++) {
            dp[i][j]=dp[i-1][j]+a[i][j];
            path[i][j]=0;
        }
        for(int j=2;j<=M;j++) {
            int foo=dp[i][j-1]+a[i][j];
            if(foo<dp[i][j]) {
                dp[i][j]=foo;
                path[i][j]=1;
            }
        }
        for(int j=M-1;j>=1;j--) {
            int foo=dp[i][j+1]+a[i][j];
            if(foo<dp[i][j]) {
                dp[i][j]=foo;
                path[i][j]=2;
            }
        }
    }

    /*for(int i=N;i>=1;i--) {
        for(int j=1;j<=M;j++)
            printf("%d ",path[i][j]);
        printf("\n");
    }*/

    dp[N][0]=0x7fffffff;
    int p=0;
    for(int i=1;i<=M;i++)
        if(dp[N][i]<dp[N][p])
            p=i;

    int __path[30000];
    int __n=0;
    int *__p=path[N]+p;
    while(*__p!=-1) {
        __path[__n++]=p;
        switch(*__p) {
            case 0:
                __p-=501;
                break;
            case 1:
                __p--;
                p--;
                break;
            case 2:
                __p++;
                p++;
                break;
        }
    }

    for(int i=__n-1;i>=0;i--)
        printf("%d\n",__path[i]);

    return 0;
}

3612

#include <stdio.h>
#include <string.h>
#include <stdlib.h>


int main() {
    int N,C,H[100001];
    scanf("%d%d",&N,&C);
    for(int i=1;i<=N;i++)
        scanf("%d",H+i);

    int *dp=(int *)malloc(sizeof(int)*101);
    memset(dp,0,sizeof(int)*101);

    for(int i=1;i<=N;i++) {
        int d[101],u[101],min;

        min=0x7fffffff;
        for(int k=1;k<=100;k++) {
            if(dp[k]-C*k<min)
                min=dp[k]-C*k;
            d[k]=min;
        }

        min=0x7fffffff;
        for(int k=100;k>=1;k--) {
            if(dp[k]+C*k<min)
                min=dp[k]+C*k;
            u[k]=min;
        }

        int *__dp=(int *)malloc(sizeof(int)*101);
        for(int k=1;k<H[i];k++)
            __dp[k]=1E9;
        for(int k=H[i];k<=100;k++) {
            int uv=u[k]-C*k;
            int dv=d[k]+C*k;
            __dp[k]=uv<dv?uv:dv;
            __dp[k]+=(k-H[i])*(k-H[i]);
        }

        free(dp);
        dp=__dp;
    }

    int result=0x7ffffff;
    for(int i=1;i<=100;i++)
        result=dp[i]<result?dp[i]:result;
    printf("%d\n",result);
    return 0;
}