首页 > ACM题库 > HDU-杭电 > HDU 3377-Plan-动态规划-[解题报告]HOJ
2014
03-16

HDU 3377-Plan-动态规划-[解题报告]HOJ

Plan

问题描述 :

One day, Resty comes to an incredible world to seek Eve — The origin of life. Lilith, the sister of Eve, comes with him. Although Resty wants to find Eve as soon as possible, Lilith likes to play games so much that you can’t make her make any move if you don’t play with her.

Now they comes to the magical world and Lilish ask Resty to play with her.

The game is following :
Now the world is divided into a m * n grids by Lilith, and Lilith gives each grid a score.
So we can use a matrix to describe it.
You should come from cell(0, 0) to cell(m-1, n-1) (Up-Left to Down-Right) and try to colloct as more score as possible.
According to Lilish’s rule, you can’t arrive at each cell more than once.

Resty knows that Lilish will be easy to find the max score, and he doesn’t want to lose the game.
So he want to find the game plan to reach the max score.

Your task is to calculate the max score that Lilish will find, the map is so small so it shouldn’t be difficult for you, right?

输入:

The input consists of more than one testdata.
Process to the END OF DATA.
For each test data :
the first live give m and n. (1<=m<=8, 1<=n<=9)
following m lines, each contain n number to give you the m*n matrix.
each number in the matrix is between -2000 and 2000

输出:

The input consists of more than one testdata.
Process to the END OF DATA.
For each test data :
the first live give m and n. (1<=m<=8, 1<=n<=9)
following m lines, each contain n number to give you the m*n matrix.
each number in the matrix is between -2000 and 2000

样例输入:

2 2
1 2
3 1
3 3
0 -20 100
1 -20 -20
1   1   1

样例输出:

Case 1: 5
Case 2: 61

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3377

题目大意:给出一个矩阵,每个点有权值,找到一条权值最大的路径连接从(1,1)到(n,n)两个点。

解题思路:通过题目大意和数据范围可以判断是连通性dp,但是和以前不同,这个是求一条路径,不是回路,对此有两种做法:

方法一:通过在矩阵上右下加上一条,通过限定加上部分边界的转移条件,可以将求路径变成求回路。

方法二:改变转移条件和答案判断条件,直接用连通性dp求解最小路径。

给出的代码采用的是第二种方法。

通过代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <stack>
#define maxn 15
#define maxk 3000000
#define maxm 1000
using namespace std;
int f[2][maxk];
int ans;
int hash[maxm];
int a[2][maxk];
int pre[2][maxk];
int map[maxn][maxn];
int n,m,e,tot,num;
int fopp(int k,int b,int x,int fx)
{
    stack <int> st;
    while (!st.empty()) st.pop();
    for (int i=k+b;;i+=b){
        int h=fx>>i*2-2&3;
        if (h==x){
           if(st.empty()) return i;
           else st.pop();
        }
        else if(h) st.push(h);
    }
}
    
void put(int x,int v)
{
     int h=x%997;
     int p=hash[h];
     while (p>0){
           if (a[e][p]==x) break;
           p=pre[e][p];
     }
     if (p==0){
        num++;
        pre[e][num]=hash[h];hash[h]=num;
        a[e][num]=x;f[e][num]=v;
     }
     else f[e][p]=max(f[e][p],v);
}


void dp(int i,int j,int x,int v)
{
     int left=x>>2*j-2&3;
     int up=x>>2*j&3;
     //printf("%d %d %d %d\n",i,j,x,v);
     //printf("%d %d\n",left,up);
     x-=(left<<2*j-2)+(up<<2*j);
     if (left+up==0){
        if (i==1&&j==1) {put(x+(1<<2*j-2),v);put(x+(2<<2*j),v);return;}
        if (i<n&&j<m) put(x+(1<<2*j-2)+(2<<2*j),v);
        put(x,v-map[i][j]);
     }
     else if(left==0||up==0){
          int temp=left+up;
          if (i==n&&j==m) ans=max(ans,v);
          if (i<n) put(x+(temp<<2*j-2),v);
          if (j<m) put(x+(temp<<2*j),v);
     }
     else if(left+up==3){
          if (left==2) put(x,v);
     } 
     else if(left+up==2){
          int t=fopp(j+1,1,2,x);
          put(x-(1<<t*2-2),v);
     }
     else if(left+up==4){
          int t=fopp(j,-1,1,x);
          put(x+(1<<t*2-2),v);
     }
}
int main(){
    int cas=0;
    while (scanf("%d%d",&n,&m)==2){
          int i,j,k,code;cas++;
          for (i=1;i<=n;i++)
              for (j=1;j<=m;j++)
                  scanf("%d",&map[i][j]);
          if (n==1&&m==1) {printf("Case %d: %d\n",cas,map[1][1]);continue;}
          memset(f,0,sizeof(f));
          memset(hash,0,sizeof(hash));
          e=0;num=0;
          put(0,0);
          ans=-100000000;
          for (i=1;i<=n;i++)
              for (j=1;j<=m;j++){
                  memset(hash,0,sizeof(hash));
                  e=1-e;tot=num;num=0;
                  for (k=1;k<=tot;k++){
                      code=a[1-e][k];
                      if (j==1)  code=code<<2;
                      dp(i,j,code,f[1-e][k]+map[i][j]);
                  }
              }
          printf("Case %d: %d\n",cas,ans);
    }
    return 0;
}

参考:http://blog.csdn.net/ruptins/article/details/20764857


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  3. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.