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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[YZOJ2035]cf263E Rhombus  

2014-10-20 19:23:44|  分类: Codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

P2035 -- Rhombus

时间限制:1500MS      内存限制:1048576KB      通过/提交人数:5/23

状态:Accepted      标签:    动态规划   小技巧   无

Description

给定一个n*m的矩阵a,其中a中的元素均为非负整数,另外有一个正整数k。定义函数

[YZOJ2035]cf263E Rhombus - Trinkle - n+e

其中x,y满足k<=x<=n-k+1,k<=y<=m-k+1

求出使f(x,y)取到最大值的(x,y)。

Input Format

第一行为三个正整数n,m,k,其中(1≤n,m≤2000, [YZOJ2035]cf263E Rhombus - Trinkle - n+e)

接下来n行,每行m个数,第i行第j个数为a[i][j],0<=a[i][j]<=10^6

Output Format

输出两个数x,y,为使f(x,y)取到最大值的(x,y),如果有多组解,输出x最小的那一个,如果有x相等时,输出y最小的那一个。

Sample Input

#1
4 4 2
1 2 3 4
1 1 1 1
2 2 2 2
4 3 2 1

#2
5 7 3
8 2 3 4 2 3 3
3 4 6 2 3 4 6
8 7 6 8 4 5 7
1 2 3 2 1 3 2
4 5 3 2 1 2 1

Sample Output

#1
3 2

#2
3 3

Hint

source:cf263E

对于i(1≤i≤10)号测试点,n,m近似于200*i

原题内存才给0.25G,因为出题人良心就给了1G。(其实出题人@ufozgg在sxbk的卡你常数)

Solution

本题有很多做法。

首先n*m的时间复杂度肯定少不了,关键是看你在程序中用了多少次for,否则调常数要调死了。。。

我的想法是,当你知道了一个菱形的sum,如果能在O(1)的时间內求出旁边相邻的菱形的sum的话就可以了。

注意到它乘的系数是线性的,差分一次就变成常数列。

于是将相邻两个菱形的sum差分,会得到如下结果:(假设k=3)

‘+’表示左边的菱形每一个格子加了几次,'-'表示右边的。算一下发现:

所以如果左边的菱形和为sum1,右边的菱形和为sum2,左右两个三角形的和分别为ta,tb,就会有sum1-sum2=ta-tb。

因此只要维护一下三角形的和就可以了。上下左右四个方向都要维护。前提是先求出横竖两个前缀和、斜着的两个前缀和,在计算sum的时候顺便可以计算三角形的和。

在第一次计算的时候,中心点为(k,k)的菱形只能先暴力。然后往下面转移四个三角形和答案,最后才能全部往右边转移,因为两种转移不一样,我觉得这样写会更好写一点。

这题毕竟是CF上面的题,我看了一下别人的代码发现有神构造,详见code_2

假设k=3

sd[][]表示

kkkk321

kkkk321

3333321

2222221

11111111

sd2[][]表示

kk321

kk321

33321

2221

111

然后加加减减就会得到答案。真是太神了!

在CF上面交代码的时候注意一下ans=0的情况。

#include<cstdio>
int aa;char ch;int F(){
while(ch=getchar(),ch<48||ch>57);aa=ch-48;
while(ch=getchar(),ch>47&&ch<58)aa=aa*10+ch-48;return aa;
}
const int N=2002;typedef long long ll;
int n,m,k,x,y,i,j,l;
ll a[N][N],b[N][N],c[N][N],d[N][N],ans0,ans,tmp[N][3],ta,tb,tc,td;
int main(){
for(n=F(),m=F(),k=F(),i=1;i<=n;i++)
for(j=1;j<=m;j++)d[i][j]=F(),
a[i][j]=a[i][j-1]+d[i][j],
b[i][j]=b[i-1][j]+d[i][j],
c[i][j]=c[i-1][j-1]+d[i][j];
for(i=n;i;i--)
for(j=1;j<=m;j++)d[i][j]+=d[i+1][j-1];
for(l=0;l<k;l++)
ta+=d[k-l][k]-d[k+1][k-l-1]+c[k+l][k]-c[k][k-l],
tb+=c[k][k+l]-c[k-l-1][k-1]+d[k+1][k+l-1]-d[k+l+1][k-1],
tc+=d[k-l][k]-d[k+1][k-l-1]+c[k][k+l]-c[k-l][k],
td+=c[k+l][k]-c[k-1][k-l-1]+d[k][k+l]-d[k+l][k],
ans0+=ta+tb-b[k+l][k]+b[k-l-1][k];
for(tmp[k][0]=ta,tmp[k][1]=tb,tmp[k][2]=ans0,i=k;i<n-k+1;i++)
ta+=c[i+k][k]-d[i-k+1][k],
tb+=d[i+1][k+k-1]-d[i+k+1][k-1]-c[i][k+k-1]+c[i-k][k-1],
td+=d[i+1][k+k-1]-d[i+k][k]+c[i+k][k]-a[i][k+k-1],
tmp[i+1][0]=ta,tmp[i+1][1]=tb,tmp[i+1][2]=tmp[i][2]+td-tc,
tc+=a[i+1][k+k-1]-c[i][k+k-1]+c[i-k+1][k]-d[i-k+1][k];
for(i=k;i<=n-k+1;i++)
for(ta=tmp[i][0],tb=tmp[i][1],ans0=tmp[i][2],ans0>ans?ans=ans0,x=i,y=k:1,j=k;j<m-k+1;j++)
tb+=c[i][j+k]-c[i-k][j]+d[i+1][j+k-1]-d[i+k][j]-b[i+k-1][j]+b[i-k][j],ans0+=tb-ta,
ta+=b[i+k-1][j+1]-b[i-k][j+1]-c[i+k-1][j]+c[i][j-k+1]-d[i-k+1][j]+d[i+1][j-k],
ans0>ans?ans=ans0,x=i,y=j+1:1;
printf("%d %d\n",x,y);
}

#include<cstdio>
typedef long long ll;
int a;char c;int F(){
while(c=getchar(),c<'0'||c>'9');a=c-48;
while(c=getchar(),c>='0'&&c<='9')a=a*10+c-48;return a;
}
const int N=2005;int n,m,k,ansx,ansy,i,j;
ll ans=-1,s[N][N],sd[N][N],sd2[N][N],cur;
int main(){
for(n=F(),m=F(),k=F(),i=1;i<=n;i++)for(j=1;j<=m;j++)s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+F();
for(i=1;i<=n;i++)for(j=1;j<=m;j++)sd[i][j]=sd[i-1][j-1]+s[i][j]-(i>k&&j>k?s[i-k][j-k]:0);
for(i=1;i<=n;i++)for(j=m;~j;j--)sd2[i][j]=sd2[i-1][j+1]+s[i][j]-(i>k&&j<=m-k?s[i-k][j+k]:0);
for(i=k;i<=n-k+1;i++)for(j=k;j<=m-k+1;j++){
cur=sd2[i+k-1][j]+sd2[i-1][j-k]-sd[i-1][j+k-1]-sd[i+k-1][j-1];
if(cur>ans)ans=cur,ansx=i,ansy=j;
}
printf("%d %d\n",ansx,ansy);
return 0;
}

  评论这张
 
阅读(95)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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