Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
 Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

网上的这个DP拓扑序列 我对它提出严重质疑

Posted by litter at 2009-09-17 20:22:35 on Problem 1191 
for  (k = 2 ; k <= n; k ++ )
      {
         for  (x1 = 1 ; x1 <= 8 ; x1 ++ )
             for  (y1 = 1 ; y1 <= 8 ; y1 ++ )
                 for  (x2 = x1; x2 <= 8 ; x2 ++ )
                     for  (y2 = y1; y2 <= 8 ; y2 ++ )
                      {
                        tmp  =  INF;
                         // 竖切 
                          for  (a = x1; a < x2; a ++ )
                          {
                            t  =  min(f[x1][y1][a][y2][k - 1 ] + s[a + 1 ][y1][x2][y2] * s[a + 1 ][y1][x2][y2]
                                , f[a + 1 ][y1][x2][y2][k - 1 ] + s[x1][y1][a][y2] * s[x1][y1][a][y2]);
                             if  (tmp  >  t) 
                                tmp  =  t;
                        } 
                         // 横切 
                          for  (b = y1; b < y2; b ++ )
                          {
                            t  =  min(f[x1][y1][x2][b][k - 1 ] + s[x1][b + 1 ][x2][y2] * s[x1][b + 1 ][x2][y2]
                                , f[x1][b + 1 ][x2][y2][k - 1 ] + s[x1][y1][x2][b] * s[x1][y1][x2][b]);
                             if  (tmp  >  t)
                                tmp  =  t;
                        } 
                        
                        f[x1][y1][x2][y2][k]  =  tmp;
                    } 
    }
Followed by:
Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator