走方格改进版dp

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 using namespace std;
 5 
 6 int num[1002][501];
 7 int a[1002][1002];
 8 
 9 int main()
10 {
11     num[1][0]=0;
12     num[2][0]=1;
13     for(int i=3;i<=1000;i++)
14     {
15         int k=0;
16         for(int j=1;j<=i/2;j++)
17         {
18             if(i%j==0)
19             num[i][k++]=j;
20         }
21     }
22     int t;
23     int n,m;
24     //freopen("aa.txt","r",stdin);
25     scanf("%d",&t);
26     while(t--)
27     {
28         scanf("%d %d",&n,&m);
29         for(int i=1;i<=n;i++)
30         for(int j=1;j<=m;j++)
31         scanf("%d",&a[i][j]);
32         for(int i=2;i<=m;i++)
33         {
34             int x=a[1][i-1];
35             int k=0;
36             while(num[i][k]!=0)
37             {
38                 if(x<a[1][num[i][k]])
39                 x=a[1][num[i][k]];
40                 k++;
41             }
42             a[1][i]+=x;
43         }
44         for(int i=2;i<=n;i++)
45         {
46             for(int j=1;j<=m;j++)
47             {
48                 if(j==1)
49                 a[i][j]+=a[i-1][j];
50                 else
51                 {
52                     int x=max(a[i][j-1],a[i-1][j]);
53                     int k=0;
54                     while(num[j][k]!=0)
55                     {
56                         if(x<a[i][num[j][k]])
57                         x=a[i][num[j][k]];
58                         k++;
59                     }
60                     a[i][j]+=x;
61                 }
62             }
63         }
64         printf("%d\n",a[n][m]);
65     }
66     return 0;
67 }