Peter算法小课堂—简单建模(3)
2023-12-15 21:28:26
国王的奖赏系列
国王的奖赏1
题目描述:
你作为战斗英雄得到国王的奖赏,可以在地图上选一块土地。地图里共n*m格土地,第x行第y列的土地格子里标记着d[x][y]的整数价值,可能出现负数。国王让你选择若干列土地,只要是连续的几列土地,你就可以都收入囊中。求你选的土地总价值最大能是多少?当然如果最大值是负数,请输出0
这道题请仔细看标红的地方,这是易错点。当然如果你看到了这几个字,在你没有思路的情况下,也可以骗一点分。读完题目,思考样例,不出意外的话你已经发现了……最大连续子序列和
最大连续子序列和有的小彭友不会,Peter算法小课堂—DP的应用-CSDN博客
#include <bits/stdc++.h>
using namespace std;
const int N=1000;
int d[N][N],clmn[N],f[N],n,m;
int main(){
freopen("reward1.in","r",stdin);
freopen("reward1.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>d[i][j];
}
}
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
clmn[j]+=d[i][j];
}
}
for(int i=1;i<=m;i++) f[i]=max(f[i-1],0)+clmn[i];
cout<<max(0,*max_element(f+1,f+1+m));
return 0;
}
?国王的奖赏2
题目描述:
你作为战斗英雄得到国王的奖赏,可以在地图上选一块土地。地图里共n*m格土地,坐标为(x,y)格子里标记着d[x][y]的整数价值。你可以选择任意的长方形土地块,收入囊中,求你选的土地总价值最大能是多少?当然如果最大值是负数,请输出0
这道题实际上就是最大子矩阵和问题,这个算法复杂度最多n^4,我们一步一步优化。
O(n^4)
那么……二维前缀和怎么算呢?
?
容斥原理解决😀
那么,随便一块长方形怎么算呢?
?
代码来咯
#include <bits/stdc++.h>
using namespace std;
const int N=500;
int s[N][N],d[N][N],n,m,ans;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>d[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
s[i][j]=d[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
}
for(int r1=1;r1<=n;r1++){
for(int r2=r1;r2<=n;r2++){
for(int c1=1;c1<=m;c1++){
for(int c2=c1;c2<=m;c2++){
ans=max(ans,s[r2][c2]+s[r1-1][c1-1]-s[r2][c1-1]-s[r1-1][c2]);
}
}
}
}
cout<<ans;
return 0;
}
?O(n^3)
枚举行数+最大子段和
#include <bits/stdc++.h>
using namespace std;
const int N=500;
int x[N][N],d[N][N],f[N],n,m,ans;
int main(){
freopen("reward2.in","r",stdin);
freopen("reward2.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>d[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
x[i][j]=x[i-1][j]+d[i][j];
}
}
for(int r1=1;r1<=n;r1++){
for(int r2=r1;r2<=n;r2++){
for(int j=1;j<=m;j++){
ans=max(ans,f[j]=max(f[j-1],0)+x[r2][j]-x[r1-1][j]);
}
}
}
cout<<ans;
return 0;
}
国王的奖赏3
题目描述:
僵尸大战你立下战功,你作为战斗英雄得到国王的奖赏,可以在一排n件绝世珠宝里挑选若干个。从左往右数第i个珠宝价值p[i]。
“你作为我国战斗英雄,本王不会亏待你!这里的宝贝你看看有喜欢的吗?挑两批带回家给你老婆吧。”国王豪爽地介绍着。
听完国王的话,你在思考“挑两批”这三个字的含义。说实话你也不敢多拿,怕遭人白眼。要不这样吧,你就挑2段:每一段至少1个珠宝,最多k个珠宝;这2段要分开,不能相邻。请问你拿走的珠宝最多价值多少?
技巧:遇到一个简单问题要分两次独立不重叠做时,可枚举分割点
#include <bits/stdc++.h>
using namespace std;
const int N=500;
int x[N],s[N],t[N],f[N],g[N],n,ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x[i];
}
s[0]=x[0]=0;
for(int i=1;i<=n;i++) s[i]=s[i-1]+x[i];
f[0]=0;
for(int i=1;i<=n;i++){
int j=max(0,i-k);
f[i]=max(f[i-1],s[i]-s[j]);
}
t[n+1]=x[n+1]=0;
for(int i=n;i>=1;i--) t[i]=t[i+1]+x[i];
g[n+1]=0;
for(int i=n;i>=1;i--){
int j=min(n+1,i+k);
g[i]=max(g[i+1],t[i]-t[j]);
}
for(int i=1;i<=n-2;i++) ans=max(ans,f[i]+g[i+2]);
cout<<ans<<endl;
return 0;
}
希望这些对大家有用,三连必回
文章来源:https://blog.csdn.net/zhang040818/article/details/135021203
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!