Mark一下， dp状态转移方程写对，可是写代码都错，poj 1651 poj 1179

dp题：

1、写状态转移方程;

2、考虑初始化边界，有意义的赋定值。还没计算的赋边界值；

3、怎么写代码自底向上计算最优值

今天做了几个基础dp，所有是dp方程写对可是初始化以及计算写错

先是poj 1651 事实上就是个赤裸裸的矩阵连乘。dp方程非常easy写出

                      dp[i][j]=min(dp[i][k]+dp[k+1][j]+r[i]*c[k]*c[j],dp[i][j]);

先贴两个个二逼的代码，mark下自己多么的二逼：

二逼一：在计算的时候使用了还没有算出来的值，模拟下就知道第一重循环里算dp[0][2]=dp[0][0]+dp[1][2];

!!!!!dp[1][2]这时候根本没有计算出来还，Tmd我就用了这个值！！！。！！！！！。！。！！。！。。！。。！！二逼啊！！！！！。。！！

#include

#include

#include

using namespace std;

const int SIZE = 100+10;

const int INF = 10000000;

int dp[SIZE][SIZE];

int r[SIZE],c[SIZE];

int main()

{

    int n;

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

    {

        for(int i=0;i

        {

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

            if(i>0)c[i-1]=r[i];

        }

        scanf("%d",&c[n-2]);

        n--;

        int ans=0;

        for(int i=0;i

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

            for(int j=i;j

            {

                for(int k=i;k

                    dp[i][j]=min(dp[i][k]+dp[k+1][j]+r[i]*c[k]*c[j],dp[i][j]);

            }

        for(int i=0;i

        {

            for(int j=0;j

                printf("%d ",dp[i][j]);

            putchar('\n');

        }

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

    }

    return 0;

}

二逼二：来回换思路的时候各种思路弄混。看凝视

#include

#include

#include

using namespace std;

const int SIZE = 100+10;

const int INF = 10000000;

int dp[SIZE][SIZE];

int r[SIZE],c[SIZE];

int main()

{

int n;

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

{

for(int i=0;i

{

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

if(i>0)c[i-1]=r[i];

}

scanf("%d",&c[n-2]);

n--;

int ans=0;

for(int i=0;i

int j;

for(int l=2;l<=n;l++)

for(int i=0;i

{

j=i+l-1;

dp[i][j]=INF;

for(int k=i;k

dp[i][j]=min(dp[i][k]+dp[k+1][j]+r[i]*c[k]*c[j],dp[i][j]);

}

/*for(int i=0;i

{

for(int j=0;j

printf("%d ",dp[i][j]);

putchar('\n');

}*/

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

}

return 0;

}

正确代码：

#include

#include

#include

using namespace std;

#define ll long long

const int SIZE = 100+10;

const int INF = 200000000;

ll dp[SIZE][SIZE];

int r[SIZE],c[SIZE];

int main()

{

int n;

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

{

for(int i=0;i

{

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

if(i>0)c[i-1]=r[i];

}

scanf("%d",&c[n-2]);

n--;

int ans=0;

for(int i=0;i<=n;i++)dp[i][i]=0;

int j;

for(int l=2;l<=n;l++)

for(int i=0;i

{

j=i+l-1;

dp[i][j]=INF;

for(int k=i;k

dp[i][j]=min(dp[i][k]+dp[k+1][j]+r[i]*c[k]*c[j],dp[i][j]);

}

printf("%lld\n",dp[0][n-1]);

}

return 0;

}

在做这个poj 1651之前  先做的poj 1179，然后过了poj 1651之后改了poj1179原来的循环次序，事实上就是类比这个poj1651,第一重循环弄成长度就可以

注意 负数乘以负数是正数 考虑最大最小值得时候一定注意

只是又一次检查下发现代码在初始化的时候冗余，精简了下。

贴代码：

#include

#include

#include

using namespace std;

#define ll long long

const int SIZE =55;

const int INF = (-2147483647 ) ;

ll dp[SIZE][SIZE],dpmin[SIZE][SIZE];

int pos[SIZE];

bool op[SIZE];

int main()

{

//freopen("poj1179.txt","r",stdin);

int n;

ll tmp1,tmp2;

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

{

for(int i=0;i

for(int i=0;i

{

scanf(" %c %lld",&op[i],&dp[i][1]);

dpmin[i][1]=dp[i][1];

}

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

for(int i=0;i

{

if(j>1)dp[i][j]=INF,dpmin[i][j]=-INF;

for(int k=1;k

{

if(op[(i+k)%n ] == 't')

{

dp[i%n][j]=max(dp[i%n][k]+dp[(i+k)%n ][j-k],dp[i%n][j]);

dpmin[i%n][j]=min(dpmin[i%n][k]+dpmin[(i+k)%n ][j-k], dpmin[i%n][j]);

}

else

{

tmp1=max(dp[i%n][k]*dp[(i+k)%n ][j-k],dpmin[i%n][k]*dpmin[(i+k)%n ][j-k]);

tmp2=max(dp[i%n][k]*dpmin[(i+k)%n ][j-k], dpmin[i%n][k]*dp[(i+k)%n ][j-k]);

tmp1=max(tmp1,tmp2);

dp[i%n][j]=max(tmp1,dp[i%n][j]);

tmp2=min(dp[i%n][k]*dp[(i+k)%n ][j-k],dpmin[i%n][k]*dpmin[(i+k)%n ][j-k]);

tmp1=min(dp[i%n][k]*dpmin[(i+k)%n ][j-k], dpmin[i%n][k]*dp[(i+k)%n ][j-k]);

tmp2=min(tmp1,tmp2);

dpmin[i%n][j]=min(dpmin[i%n][j],tmp2);

}

}

}

int cnt=0;

ll ans=INF;

for(int i=0;i

{

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

}

for(int i=0;i

if(ans == dp[i][n])

pos[cnt++]=i+1;

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

for(int i=0;i

if(i == cnt-1)printf("%d\n",pos[i]);

else printf("%d ",pos[i]);

}

return 0;

}

精彩链接