上文链接
最大加权矩形
我们言归正传，首先我们可以想到，这道题其实是要求一个和，那么我们不难想到可以用前缀和来解决，但是这样的时间复杂度过于高了，那么我们怎么办呢？其实我们这里可以用一点最大字段和的知识。
最大字段和
给定一个长为 n 的序列，任意选择其中连续的 x（0≤𝑥≤n）项所确定的一段更短的连续序列叫作一个子段。一个子段的得分为其每个元素之和，请求出原序列的最大子段和。
我们正常来说应该是用枚举的思想，但是这样的时间复杂度为O(n2),如果n稍微大一点就过不了了，那么我们还是考虑动态规划。
首先我们可以想到 d p [ i ] dp[i] dp[i]可能与 d p [ i − 1 ] dp[i-1] dp[i−1]和 a [ i ] a[i] a[i]有关，那么我们就可以想到这个关系式 d p [ i ] = m a x ( d p [ i − 1 ] + a [ i ] , a [ i ] ) dp[i]=max(dp[i-1]+a[i],a[i]) dp[i]=max(dp[i−1]+a[i],a[i])
那么我们就可以写出以下代码
#include<bits/stdc++.h>
using namespace std;
long long a[1000000],dp[1000000],n,maxn=0;
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];dp[i]=0;}for(int i=1;i<=n;i++){dp[i]=max(dp[i-1]+a[i],a[i]);if(dp[i]>maxn){maxn=dp[i];}}cout<<maxn;return 0;
}
这样我们就可以在O(n)的时间复杂度里求完答案
最大子矩阵和和最大字段和的关联
讲了这么多，我们该怎么用呢？
其实我们可以枚举一个上下边界，然后中间就先用前缀和解出中间的值再用最大字段和的方法来解决，这样的时间复杂度就为O(n3），显然可以通过
那么我们就可以得到以下转换代码
d p [ k ] = m a x ( d p [ k − 1 ] + ( t o t [ j ] [ k ] − t o t [ i − 1 ] [ k ] ) , ( t o t [ j ] [ k ] − t o t [ i − 1 ] [ k ] ) ) ; dp[k]=max(dp[k-1]+(tot[j][k]-tot[i-1][k]),(tot[j][k]-tot[i-1][k])); dp[k]=max(dp[k−1]+(tot[j][k]−tot[i−1][k]),(tot[j][k]−tot[i−1][k]));
那么我们现在就好处理了
代码如下
#include<bits/stdc++.h>
using namespace std;int mp[310][310],tot[310][310];
int dp[310],maxn=INT_MIN;
int main(){int n;cin>>n;for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){cin>>mp[i][j];tot[i][j]=tot[i-1][j]+mp[i][j];}}for (int i=1;i<=n;i++){for (int j=i;j<=n;j++){for (int k=1;k<=n;k++){dp[k]=tot[j][k]-tot[i-1][k];}for (int k=1;k<=n;k++){dp[k]=max(dp[k-1]+(tot[j][k]-tot[i-1][k]),(tot[j][k]-tot[i-1][k]));maxn=max(dp[k],maxn);}}}cout<<maxn;return 0;
}
最大全1子矩阵
给定一个01矩阵，求其最大的全1子矩阵。
第一行n,m。 后面n行每行m个数描述这个矩阵
最大子矩阵的面积
输入数据 1
3 4
1 1 1 1
1 1 1 1
1 1 1 0
输出数据 1
9
Limitation
对于100%的数据，1<=n,m<=300
思路
这道题其实和上一道题其实差不多还是正常的进行判断，然后在进行dp的时候只需要进行判断，看看是不是都是1就可以了
代码如下
#include<bits/stdc++.h>
using namespace std;int mp[310][310],tot[310][310];
int dp[310],maxn=0;
int main(){int n,m;cin>>n>>m;for (int i=1;i<=n;i++){for (int j=1;j<=m;j++){cin>>mp[i][j];tot[i][j]=tot[i-1][j]+mp[i][j];}}for (int i=0;i<n;i++){//上边界 for (int j=i+1;j<=n;j++){//下边界 memset(dp,0,sizeof(dp));for (int k=1;k<=m;k++){if (tot[j][k]-tot[i][k]==j-i){dp[k]=dp[k-1]+(tot[j][k]-tot[i][k]);maxn=max(maxn,dp[k]);}} }}cout<<maxn;return 0;
}
穿衣服
Description
wjq是一名来自520宿舍的漂亮妹子，她喜欢穿的很性感。 wjq刚刚从床上起来，喜欢性感的她要去她寝室的不同位置去拿衣服，可是她的舍友把她的衣服丢的到处都是，黑丝，白丝，制服等衣服散在不同的位置上，wjq只好挨个去拿。 520宿舍可以看作是一个n行m列的矩形，wjq在(0,0)这个格子（位于宿舍的左上角），寝室的门在(n-1,m-1)这个格子。每次wkc可以向相邻的格子走一步，走到某个格子时，她会穿起这个格子的衣服。wjc由于没有穿鞋，而且用她的粉粉嫩嫩的脚走起来非常的不舒服，然而鞋又在寝室门口，所以她想走一条最短路到教室的门口，但是性感度太少了她自己又不舒服，所以她决定走一条性感程度最高的最短路线(即保证路径最短的前提下性感程度最高)，你能帮帮她吗？
Input
第一行三个整数n,m,k。 接下来k行，每行三个整数a,b,c，表示在(a,b)这个格子的衣服的性感程度为c。
Output
输出1个整数，表示wjq的最大性感程度。
Samples
输入数据 1
2 2 2
0 0 1
1 1 1
输出数据 1
2
n,m>=10*9,k>=8000。
思路
如果正常来说，我们肯定使用二维dp来做他，但是可以看到n和m的值非常的大，空间肯定要爆，同时这道题我们又不能用滚动数组来压缩，所以我们只能采取其他的思路
首先我们来想想最短路的问题，不难想到，只要wjq不往左或上走，就一定是最短路。
然后我们再来想想dp的问题，首先我们知道，当前的这一个点只能从这个点的左上方的区域转移而来，那么我们只需要对每一个点进行遍历。然后去找在它左上方的点就可以了。
但是我们又会想到，这样写出来的dp可能有一些值没有被算到，所以我们就需要先对每一个点进行排序，按照从左上方到右下方的顺序来排序。
#include<bits/stdc++.h>
using namespace std;struct f{int x,y;int num;
}a[8000];bool cmp(f a1,f a2){if (a1.y!=a2.y)return a1.y<a2.y;else return a1.x<a2.x;
}
int dp[8000],maxn=INT_MIN;
int main(){int n,m,k;cin>>n>>m>>k;for (int i=1;i<=k;i++){cin>>a[i].x>>a[i].y>>a[i].num;}sort(a+1,a+1+k,cmp);for (int i=1;i<=k;i++){//当前转移的值 dp[i]=a[i].num;for (int j=1;j<=k;j++){if (a[j].x<=a[i].x&&j!=i)dp[i]=max(dp[i],dp[j]+a[i].num);}maxn=max(maxn,dp[i]);}cout<<maxn; return 0;
}
