Problem Description
Passing through the valley means leaving the great devil lemon It's infinitely close !

But who would have thought ,yifenfei After killing some of them , But once again facing the test of the great labyrinth of fate , This is the devil lemon Another organ set up . Need to know , No matter who , If you're trapped in a maze 1 hours , There is no doubt that he will die !

pitiful yifenfei In order to save them MM, I jumped into the maze without hesitation . Let's help him !

The great labyrinth of destiny can be seen as a two-dimensional grid array , As shown in the figure below :

H" title="Problem H">

yifenfei It started in the upper left corner , The goal, of course, is to reach the location of the great devil in the lower right corner . Every grid in the maze is cursed by the goddess of luck or the demon of pain , So each grid has a value , Go there and get the corresponding value automatically .

Now it is stipulated that yifenfei You can only go right or down , You can only go one space at a time . But if you go right , Then you can walk one grid at a time or go to the grid where the number of columns in the row is a multiple of the number of columns in the current row , namely : If the current grid is (x,y), The next step could be (x+1,y),(x,y+1) perhaps (x,y*k)
among k>1.

In order to be able to eliminate the devil to the greatest extent lemon,yifenfei Hope to be able to get the maximum lucky value in this big maze of fate .

H" title="Problem H">

Input
The input data is first an integer C, Number of groups representing test data .

The first line of each set of test data is two integers n,m, It represents the number of rows and columns respectively (1<=n<=20,10<=m<=1000);

Next is n Row data , Each row contains m It's an integer , Express n That's ok m The lucky value corresponding to the lattice of the column K ( |k|<100 ).

Output
Please output an integer for each group of test data , Express yifenfei The maximum lucky value you can get .
Sample Input
1
3 8
9 10 10 10
10 -10 10 10
10 -11 -1 0
2 11 10 -20
-11 -11 10
11 2 10 -10 -10
Sample Output
52
The question : A little ;
Their thinking : It feels like a digital triangle problem , There's a bottom-up traversal , It's kind of nice to go right k Times the number of steps , But the title says K>1; But when judging the conditions :
for(int
k=2;k<=j;k++)

      
if(j%k==0)

         d=max(d,dp[i][j/k]);// Compared with those who take a few steps, the biggest
here k There has to be something equal to j When , What's the meaning , It's not rigorous ;
Sentiment : I think I have a sense of achievement
Code :
#include

#include

#include

#define M 1500

#define N 30

#define INT 0x3f3f3f3f

using namespace std;

int t,n,m,dp[N][M];

int main()

{

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

   
scanf("%d",&t);

   
while(t--)

    {

       
scanf("%d%d",&n,&m);

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

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

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

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

       
{

           
dp[i][0]=-INT;

           
dp[0][i]=-INT;

       
}

       
dp[0][1]=dp[1][0]=0;

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

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

           
{

               
if(i==1&&j==1)// The first step is not state transition

                   
dp[i][j]=dp[i][j];

               
else if(j==1)// The one on the far left can't be transferred to the right

                   
dp[i][j]+=dp[i-1][j];

               
else

               
{

                   
int d=dp[i][j-1];// It's a step to the right

                   
for(int k=2;k<=j;k++)

                   
if(j%k==0)

                       
d=max(d,dp[i][j/k]);// Compared with those who take a few steps, the biggest

                   
if(i==1)

                       
dp[i][j]+=d;

                   
else

                       
dp[i][j]+=max(d,dp[i-1][j]);

               
}

           
}

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

           
//{

           
//    for(int
j=1;j<=m;j++)

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

           
//   
printf("\n");

           
//}

           
//printf("\n");

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

    }

    return
0;

}

Problem H More articles about

  1. experiment 12:Problem H: Integer array operator overload

    Home Web Board ProblemSet Standing Status Statistics   Problem H: Integer array operator overload Problem H: Integer array operator overload Tim ...

  2. The Ninth Hunan Collegiate Programming Contest (2013) Problem H

    Problem H High bridge, low bridge Q: There are one high bridge and one low bridge across the river. ...

  3. Gym 100531H Problem H. Hiking in the Hills Two points

    Problem H. Hiking in the Hills Topic linking : http://codeforces.com/gym/100531/attachments Description Helen ...

  4. Codeforces Gym 100610 Problem H. Horrible Truth fiddle

    Problem H. Horrible Truth Time Limit: 1 Sec Memory Limit: 256 MB Topic linking http://codeforces.com/gym/1006 ...

  5. Codeforces Gym 100342H Problem H. Hard Test Construction question , Caddie jestra

    Problem H. Hard TestTime Limit: 20 Sec Memory Limit: 256 MB Topic linking http://codeforces.com/gym/100342/at ...

  6. Qingbei school entrance test P4751 H’s problem(h)

    P4751 H’s problem(h)  Time : 1000ms / Space : 655360KiB / Java Class name : Main background Winter camp entrance test describe Small H It's a girl who likes shopping , But because of College ...

  7. 2013-2014 ACM-ICPC, NEERC, Southern Subregional Contest Problem H. Password Service dp

    Problem H. Password Service Topic linking : http://www.codeforces.com/gym/100253 Description Startups are here ...

  8. Western Subregional of NEERC, Minsk, Wednesday, November 4, 2015 Problem H. Parallel Worlds Computational geometry

    Problem H. Parallel Worlds Topic linking : http://opentrains.snarknews.info/~ejudge/team.cgi?SID=c75360ed7f2c7 ...

  9. 2010-2011 ACM-ICPC, NEERC, Moscow Subregional Contest Problem H. Hometask Water problem

    Problem H. Hometask Topic linking : http://codeforces.com/gym/100714 Description Kolya is still trying to pass ...

Random recommendation

  1. [LintCode] Best Time to Buy and Sell Stock The best time to buy and sell stocks

    Say you have an array for which the ith element is the price of a given stock on day i. If you were ...

  2. Java data structure —— Dictionary tree TRIE

    Also known as word search tree ,Trie Trees , It's a tree structure , It's a variation of the hash tree . The typical application is for statistics , Sort and save a lot of strings ( But it's not just about strings ), So it is often used in text word frequency statistics by search engine system . Its advantages are : Take advantage of the public ...

  3. be based on HTML5 Of WebGL Design the tower of Hanoi 3D game

    Here we're going to construct a model based on HT for Web Of HTML5+JavaScript To realize the tower of Hanoi game . http://hightopo.com/demo/hanoi_20151106/index.html ...

  4. VC ++ MFC activex Control to get the connected VPN Information

    vc++  MFC Conduct activex   Control development steps do not have to write , Just a simple explanation of the method , And the specific code : The library used is windows Systematic  rasapi32.dll Remember that the header files you need to add are as follows ...

  5. JavaScript The rules of Library developers

    For details, please click 1. Keep it non-invasive my HTML I don't want to know your JavaScript Code . 2. Modification and extension are strictly prohibited Object.prototype! This is very important , So there needs to be a rule that's all about it . The object is Ja ...

  6. UITabBarController note ( 3、 ... and ) UITabBarController coordination UINavigationController Use

    Build an empty one iOS engineering - (BOOL)application:(UIApplication *)application didFinishLaunchingWithOptions:(NSDictiona ...

  7. HTTPS Man in the middle attacks practice ( principle &#183; practice )

      Preface I saw... A long time ago HTTPS Introduction to , And I've learned about TLS The details of , Also believe in using HTTPS It is relatively safe and reliable . Until a while ago in the verification https When the proxy channel is connected , Set the MITM Environmental Science , Only to find out that the truth is not what I think . because ...

  8. solve eclipse export javadoc At the time of the “ error : code GBK Unmapped characters of ” problem ( turn )

    http://blog.csdn.net/psy1100/article/details/51179342 Today, I'm going to give you my life API Interface and MODEL Lead out a java doc Reference documents , But when you export it ...

  9. C# webbrowser Determine whether the page is loaded

    private void Form1_Load(object sender, EventArgs e) { webalipay.Url = new Uri("https://authzth. ...

  10. Java Compress / decompression .zip、.tar.gz、.tar.bz2( Support Chinese )

    In this paper, Java Compress / decompression .zip..tar.gz..tar.bz2 The way . about zip file : Use java.util.zip.ZipEntry and java.util.zip.ZipFile, By setting ...