好贷网好贷款

HDU 4708

发布时间:2016-12-5 10:35:21 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 4708",主要涉及到HDU 4708方面的内容,对于HDU 4708感兴趣的同学可以参考一下。

题目 题意:有一个n*n的矩阵(n%2==1),把它想象成一圈一圈的,然后每次每一圈可以逆时针和顺时针旋转一个单位,然后求主对角线和斜对角线元素之和,是和最大,并且在最大值里,旋转次数最小 想法:可以预处理出每一圈的元素,要所有和最大,很明显每一圈的四个顶点和要最大,然后就YY吧 #include<stdio.h> #include<string.h> #include<vector> #include<queue> #include<algorithm> using namespace std; struct sy { int sum,t; }; int n; int map[10][10]; vector<int>e[10]; inline void bfs() { int m=3; e[1].push_back(map[(1+n)/2][(1+n)/2]); for(int i=2;i<=(1+n)/2;i++) { //int m=3; int x=(1+n)/2-(i-1); int y=x; for(int j=0;j<m;j++) { e[i].push_back(map[x][y++]); } y--;x++; for(int j=1;j<m;j++) { e[i].push_back(map[x++][y]); } x--;y--;; for(int j=1;j<m;j++) { e[i].push_back(map[x][y--]); } y++,x--; for(int j=2;j<m;j++) { e[i].push_back(map[x--][y]); } m+=2; } } int main() { while(scanf("%d",&n)&&n) { for(int i=0;i<9;i++) e[i].clear(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&map[i][j]); bfs(); /* for(int i=1;i<=(1+n)/2;i++) { for(int j=0;j<e[i].size();j++) printf("%d ",e[i][j]); printf("\n"); } */ int sum=e[1][0],q=0; vector<sy>ans[10][2]; int num[10]={0,0,2,4,6,8,10,12}; for(int i=(1+n)/2;i>1;i--) { for(int j=0;j<num[i];j++) { sy r; r.sum=e[i][j]+e[i][j+num[i]]+e[i][j+num[i]*2]+e[i][j+num[i]*3]; r.t=num[i]-j;//注意不是j // printf("%d \n",r.sum); ans[i][0].push_back(r); } int temp=-(~0U>>1),w=100; //printf("%d\n",temp); for(int j=0;j<ans[i][0].size();j++) { if(ans[i][0][j].sum>temp) temp=ans[i][0][j].sum,w=ans[i][0][j].t; if(ans[i][0][j].sum==temp) w=min(w,ans[i][0][j].t); } for(int j=0;j<num[i];j++) { sy r; r.sum=e[i][j]+e[i][j-num[i]+e[i].size()]+e[i][j-num[i]*2+e[i].size()]+e[i][j-num[i]*3+e[i].size()]; r.t=j; ans[i][1].push_back(r); } for(int j=0;j<ans[i][1].size();j++) { if(ans[i][1][j].sum>temp) temp=ans[i][1][j].sum,w=ans[i][1][j].t; if(ans[i][1][j].sum==temp) w=min(ans[i][1][j].t,w); } sum+=temp,q+=w; } printf("%d %d\n",sum,q); } }

上一篇:后缀自动机)
下一篇:apache防止多线程下载的配置方法

相关文章

关键词: HDU 4708

相关评论