【NYOJ61】传纸条(双线DP)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 01 月 10 日

/* NYOJ61传纸条双线DP,大概思路如下:
* 首先考虑题意是从左上角传到右下角,再从右下角传到左上角,并且不能重复路线上任何点,除起始点和终点外
* 这样问题就可以转化为从起点双线走向终点,双线不相交。类似于单线DP,我们可以写出双线DP方程
* 针对该为题我们唯一需要添加的就是限制条件,不能让此双线相交。
* 状态转移方程:
* d[k,x1,y1,x2,y2]=max{ d[k-1,x1-1,y1,x2-1,y2], d[k-1,x1-1,y1,x2,y2-1] ,
* d[k-1,x1,y1-1,x2-1,y2], d[k-1,x1,y1-1,x2,y2-1] }
* 其中(x1,y1)、(x2,y2)分别为双线DP的在第K步的时候纸条所处的同学位置,并且x1!=x2 && y1!=y2 。
* 但是这样一来会发现内存在有限制性OJ会超出,所以需要进行内存优化。我们发现x1=k-y1,x2=k-y2,所以
* 我们可以把五维数组缩减至三维,该优化极其显著。但如果看过我上一期的解题报告的细心的同学学会滚动
* 数组后,会发现该题同样可以试用滚动数组,因为动态规划方程显示了该题解过程只使用了第K,K-1两维数组
* 所以我们可以进一步优化,至此内存方面优化以接近极限。使用DP算法决定了时间上的优化基本无法进行。
* 同样的该题为了同学们理解方便,没有使用滚动数组,也先不另外附出(最后附原因),请自行实践。
*/

#include <iostream>  
#include <cstring>  
#include<time.h>  
using namespace std;  
int a[51][51];  
int d[103][51][51];  
int judagemax(int a,int b)  
{   return a> b ? a : b; }  
int main()  
{     
    int n;  
    cin>>n;  
    while(n--)  
    {  
        memset(a,0,sizeof(a));  
        memset(d,0,sizeof(d));  
        int row,col;  
        cin>>row>>col;  
        for(int i=1;i<=row;i++)  
            for (int j=1;j<=col;j++)  
            {cin>>a[i][j];}  
        d[2][1][1]=2*a[1][1];  
        d[row+col][row][row]=a[row][col];  
        for (int k=3;k<row+col;k++)  
            for(int i=1;i<=row;i++)  
                for (int j=1;j<=row;j++)   
                {  
                    if(k-i<1 || k-j<1 ) break;  
                    if(i==j) continue;  
                    if(k-j>col || k-i>col) continue;  
                    d[k][i][j] =judagemax(d[k-1][i-1][j],d[k-1][i-1][j-1]);  
                    d[k][i][j] =judagemax(d[k][i][j],d[k-1][i][j-1]);  
                    d[k][i][j] =judagemax(d[k][i][j],d[k-1][i][j]);  
                    d[k][i][j] += a[i][k-i]+a[j][k-j];  
                }  
        int rc=row+col;  
        d[rc][row][row] =judagemax(d[rc-1][row-1][row],d[rc-1][row-1][row-1]);  
        d[rc][row][row] =judagemax(d[rc][row][row],d[rc-1][row][row-1]);  
        d[rc][row][row] =judagemax(d[rc][row][row],d[rc-1][row][row]);  
        d[rc][row][row] += 2*a[row][col];  
        cout<<d[row+col][row][row]<<endl;  
    }  
    return 0;  
}    
/* 
 *  ps:该题其实写的时候花了个多小时,但调试结果竟然用了天,因为是OI上的题,没有地方提交,在网上 
 *      找了一个所谓的AC程序,发现自己的程序与之不同,然后两天里人工写了N多组数据,测试了N多次,也 
 *      也没能搞明白哪里出错,最终无法与张云聪联系,才找到一个OJ系统上有该题,提交AC,网上找的那 
 *      两个程序都是错解……心里那个恨啊。明白一个道理,敢贴自己博客里的所谓AC程序也未必是对的, 
 *      有时候也需要相信自己的逻辑和自己写出的程序。以此共鉴。‘ 
 *      两天被此题搞的十分疲惫,就不写滚动数组了。 
 */  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期六, 2017 年 10 月 21 日