题目描述
blablabla
样例
const int N=110;
long long f[110][110][110];
inline long long Max(long long x,long long y){
if(x>y) return x;
return y;
}
class Solution {
public:
long long maximumScore(vector<vector<int>>& grid) {
int n=grid.size(),m=grid[0].size();
vector<vector<long long>> s(m+10,vector<long long>(n+10));
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++)
s[i][j]=s[i][j-1]+grid[j-1][i-1];
}
vector<long long> mx(n+10);
for(int i=2;i<=m;i++)
{
vector<long long> mx1(n+10);
for(int j=0;j<=n;j++)//当前列
{
for(int k=0;k<=n;k++) f[i][k][j]=0;
for(int k=0;k<=n;k++)//前一列
{
if(k>=j){
f[i][k][j]=Max(f[i][k][j],mx[k]+(s[i][k]-s[i][j]));
mx1[j]=Max(mx1[j],f[i][k][j]);
continue;
}
for(int o=0;o<=n;o++)//前前一列
{
long long w=0;
if(o<j)
{
w+=(s[i-1][j]-s[i-1][Max(o,k)]);
}
f[i][k][j]=Max(f[i][k][j],f[i-1][o][k]+w);
}
mx1[j]=Max(mx1[j],f[i][k][j]);
}
}
swap(mx1,mx);
}
long long res=0;
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++)
res=Max(res,f[m][j][i]);
}
return res;
}
};
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla