1 //Accepted    400 KB    109 ms 2 //dp线性 3 //dp[i][j]=max(dp[i-1][k]+a[i][j-k]) 4 //在前i门课上花j天得到的最大分数，等于max(在前i-1门课上花k天+在第i门课上花j-k天得到的分数) 5 #include <cstdio> 6 #include <cstring> 7 #include <iostream> 8 #include <queue> 9 #include <cmath>10 #include <algorithm>11 using namespace std;12 /**13   * This is a documentation comment block14   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！15   * @authr songt16   */17 const int imax_n = 105;18 int a[imax_n][imax_n];19 int dp[imax_n][imax_n];20 int n,m;21 int max(int a,int b)22 {23     return a>b?a:b;24 }25 void Dp()26 {27     memset(dp,0,sizeof(dp));28     for (int i=1;i<=n;i++)29     {30         for (int j=1;j<=m;j++)31         {32             for (int k=0;k<=j;k++)33             dp[i][j]=max(dp[i][j],dp[i-1][k]+a[i][j-k]);34         }35     }36     printf("%d\n",dp[n][m]);37 }38 int main()39 {40     while (scanf("%d%d",&n,&m),n+m)41     {42         memset(a,0,sizeof(a));43         for (int i=1;i<=n;i++)44         for (int j=1;j<=m;j++)45         scanf("%d",&a[i][j]);46         Dp();47     }48     return 0;49 }