题意:给出一个n*n的矩阵,旋转每一圈数字,求出对角线可能的最大值,以及转到最大时的最小距离。
只要分析每一层就可以了,本来想用地址传递二维数组,发现行不通,改了一下就行了。
这里有个坑,比如:
1 1 9 9 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
很明显最大的就是将一个9转到矩阵角,而这里更新最大值时很容易把另一种情况屏蔽掉,从而错过了更少步骤达到最大值的方法。
代码:
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: 3.cpp
* Create Date: 2013-09-08 14:21:58
* Descripton: simulate
*/
#include <cstdio>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
const int MAXN = 100;
int a[MAXN][MAXN];
int n, sum, cnt;
void solve(int k, int l) {
int tmp = -0xffffff, tt = 0;
rep(i, l - 1) {
int t = a[k][k + i] + a[k + i][k + l - 1] + a[k + l - i - 1][k + 0] + a[k + l - 1][k + l - i - 1];
if (tmp <= t) {
if (tmp == t)
tt = min(tt, min(i, l - i - 1));
else
tt = min(i, l - i - 1);
tmp = t;
}
}
sum += tmp;
cnt += tt;
}
int main() {
while (scanf("%d", &n) && n) {
rep(i, n) rep(j, n)
scanf("%d", &a[i][j]);
int l = n / 2;
sum = a[l][l];
cnt = 0;
rep(i, l)
solve(i, n - 2 * i);
printf("%d %d\n", sum, cnt);
}
return 0;
}
分享到:
相关推荐
在webDIY 和DIY中总结的专题训练
HDU2013暑期多校联合训练第一场0723-解题报告和标程
离线OJ题库(HDU ZJU等,部分有答案),需联网。
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
hdu动态规划算法集锦
收集的部分HDOJ杭电ACM题的代码 大牛勿下 全是基础供初级acmer使用
HDU的一题........HDU DP动态规
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
ACM HDU题目分类,我自己总结的大概只有十来个吧
杭电ACMhdu1163
HDU1059的代码
HDU 动态规划(46道题目
100道 acm C语言 hdu 解题报告
hdu1001解题报告
hdu 1574 passed sorce
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
ACM ICPC HDOJ 1005
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
hdu 1005.比较简单的一道题,有兴趣的可以看看。