//Accepted 400 KB 109 ms //dp线性 //dp[i][j]=max(dp[i-1][k]+a[i][j-k]) //在前i门课上花j天得到的最大分数,等于max(在前i-1门课上花k天+在第i门课上花j-k天得到的分数) #include <cstdio> #include <cstring> #include <iostream> #include <queue> #include <cmath> #include <algorithm> using namespace std; /** * This is a documentation comment block * 如果有一天你坚持不下去了,就想想你为什么走到这儿! * @authr songt */ ; int a[imax_n][imax_n]; int dp[imax_n][imax_n]; int n,m; int max(int a,int b) { return a>b?a:b; } void Dp() { memset(dp,,sizeof(dp)); ;i<=n;i++) { ;j<=m;j++) { ;k<=j;k++) dp[i][j]=max(dp[i][j],dp[i-][k]+a[i][j-k]); } } printf("%d\n",dp[n][m]); } int main() { while (scanf("%d%d",&n,&m),n+m) { memset(a,,sizeof(a)); ;i<=n;i++) ;j<=m;j++) scanf("%d",&a[i][j]); Dp(); } ; }