注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1177][Apio2009]Oil  

2014-12-07 21:46:47|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1177: [Apio2009]Oil

一开始忽略了两种情况。。
数据范围似乎是N<=1500?
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N = 1500+100;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
int n,m,K;
int map[N][N],sumk[N][N],tmp[N][N];
int maxf[N][N],maxb[N][N],maxu[N][N],maxd[N][N];
int maxfu[N][N],maxbu[N][N],maxfd[N][N],maxbd[N][N];
int main(){
freopen("in.txt","r",stdin);
int i,j;
n = scan();m = scan();K = scan();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
map[i][j] = scan();
tmp[i][j] = map[i][j]-tmp[i-1][j-1]+tmp[i][j-1]+tmp[i-1][j];
}
for(i=1;i+K-1<=n;i++){
for(j=1;j+K-1<=m;j++){
sumk[i][j] = tmp[i+K-1][j+K-1] - tmp[i+K-1][j-1] - tmp[i-1][j+K-1] + tmp[i-1][j-1];
maxf[i][j] = max(sumk[i][j], maxf[i][j-1]);
maxfu[i][j] = max(maxf[i][j],maxfu[i-1][j]);
maxu[i][j] = max(sumk[i][j], maxu[i-1][j]);
}
for(j=m-K+1;j;j--){
maxb[i][j] = max(sumk[i][j], maxb[i][j+1]);
maxbu[i][j] = max(maxb[i][j],maxbu[i-1][j]);
}
}
/*
for(i=1;i+K-1<=n;i++){
for(j=1;j+K-1<=m;j++)
printf("%d ",tmp[i][j]);
printf("\n");
}*/
for(i=n-K+1;i;i--){
for(j=1;j+K-1<=m;j++){
maxfd[i][j] = max(maxf[i][j],maxfd[i+1][j]);
maxd[i][j] = max(sumk[i][j], maxd[i+1][j]);
}
for(j=m-K+1;j;j--)maxbd[i][j] = max(maxb[i][j],maxbd[i+1][j]);
}
//[1,i-1][i,n]
//[1,j-1][j,n]
int ans = 0;
for(i=K+1;i+K-1<=n;i++){
for(j=K+1;j+K-1<=m;j++){
ans = max(ans,maxfu[i-K][j-K] + maxfd[i][j-K] + maxbd[1][j]);
ans = max(ans,maxfd[1][j-K] + maxbu[i-K][j] + maxbd[i][j]);
ans = max(ans,maxfu[i-K][j-K] + maxbu[i-K][j] + maxbd[i][1]);
ans = max(ans,maxbu[i-K][1] + maxfd[i][j-K] + maxbd[i][j]);
}
}
int temp;
for(i=K+1;i+K-1<=n;i++){
temp=0;
for(j=i+K;j+K-1<=n;j++){
temp = max(temp,maxb[j-K][1]);
if(j-i >= K)ans = max(ans,temp + maxbu[i-K][1] + maxbd[j][1]);
}
}
for(i=K+1;i+K-1<=m;i++){
temp=0;
for(j=i+K;j+K-1<=m;j++){
temp = max(temp,maxd[1][j-K]);
if(j-i >= K)ans = max(ans,temp + maxfd[1][i-K] + maxbd[1][j]);
}
}
printf("%d\n",ans);
return 0;
}

题解:
DP+分类讨论。
用两条线把矩阵分成三块,有六种分法,一条竖线一条横(4),两条线一样(2)
枚举两条线就行了。
细节非常蛋疼……
  评论这张
 
阅读(637)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017