hdu 2571

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

其实，只要把状态转移方程写出来就ok了：dp[i][j]=max{dp[i][j],dp[i-1][j]+map[i][j],dp[i][j-1]+map[i][j],dp[i][k]+map[i][j](j%k==0)};

View Code

 1 #include<iostream>
 2 #include<algorithm>
 3 const int inf=0x7fffff;
 4 using namespace std;
 5 
 6 int map[22][1010];
 7 int dp[22][1010];
 8 
 9 int main(){
10     int _case;
11     scanf("%d",&_case);
12     while(_case--){
13         int n,m;
14         scanf("%d%d",&n,&m);
15         for(int i=1;i<=n;i++){
16             for(int j=1;j<=m;j++){
17                 scanf("%d",&map[i][j]);
18             }
19         }
20         for(int i=0;i<=n;i++){
21             for(int j=0;j<=m;j++){
22                 dp[i][j]=-inf;
23             }
24         }
25         dp[1][1]=map[1][1];
26         for(int i=1;i<=n;i++){
27             for(int j=1;j<=m;j++){
28                 dp[i][j+1]=max(dp[i][j+1],dp[i][j]+map[i][j+1]);
29                 dp[i+1][j]=max(dp[i+1][j],dp[i][j]+map[i+1][j]);
30                 int k=2;
31                 while(k*j<=m){
32                     int p=k*j;
33                     dp[i][p]=max(dp[i][p],dp[i][j]+map[i][p]);
34                     k++;
35                 }
36             }
37         }
38         printf("%d\n",dp[n][m]);
39     }
40     return 0;
41 }