poj-3666 【对dp子状态无后效性的理解】

题目链接

错解：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

typedef long long LL;

const int N=;

int a[N];

int m[N][N]; // dp[i][j] 状态结尾的值

LL dp[N][N];// 前i个元素有序最大值小于等于a[j]的最值

int n;

int main ()

{

    while (~scanf ("%d",&n) ) {

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

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

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

            for (int j=;j<=n;j++) {

                m[i][j]=a[i];

                if (a[i]>a[j]) m[i][j]=a[j];

                if (a[i]<m[i-][j]) m[i][j]=m[i-][j];

                dp[i][j]=dp[i-][j]+abs (a[i]-m[i][j]);

                cout<<"i: "<<i<<" j: "<<a[j]<<" "<<dp[i][j]<<endl;

            }

        LL ans=dp[n][];

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

            ans=min (ans,dp[n][i]);

        printf("%lld\n",ans);

    }

    return ;

}

/* 错误的例子2 5 2 2 10

因为定义的状态是 前n个元素小于等于a[j]的最小次数

dp[3][2](小于等于5)最优解有 2 5 5 和 2 2 2

这两个状态不能合并因为对后面的影响是不一样的

应该重新定义状态 dp[i][j]: 前n个元素有序最大元素是a[j]的最优解

*/

正解：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

typedef long long LL;

const int N=;

int a[N],b[N];

LL dp[N][N]; //前i个元素以a[j]结尾的最值

int n;

int main ()

{

    while (~scanf ("%d",&n)) {

        memset (dp,0x3f,sizeof(dp));

        for (int i=;i<=n;i++) {

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

            b[i]=a[i];

        }

        sort (b+,b++n);

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

            for (int j=;j<=n;j++) {

                dp[i][j]=abs(a[i]-b[j]);

                if (i!=) dp[i][j]+=dp[i-][j];

                dp[i][j]=min (dp[i][j-],dp[i][j]);

            }

        printf("%d\n",dp[n][n]);

    }

    return ;

}

对于动态规划的理解我还需要加强。。。