| 题目名称 | 652. 数字填充 |
|---|---|
| 输入输出 | coupons.in/out |
| 难度等级 | ★ |
| 时间限制 | 5000 ms (5 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2012-03-16加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：23， 提交：25， 通过率：92% | ||||
 Launcher |
100 | 0.001 s | 0.27 MiB | C++ |
 QhelDIV |
100 | 0.001 s | 0.27 MiB | C++ |
 4154 |
100 | 0.002 s | 0.15 MiB | Pascal |
 Makazeu |
100 | 0.002 s | 0.26 MiB | C++ |
 Czb。 |
100 | 0.002 s | 0.26 MiB | C++ |
 Riolu |
100 | 0.002 s | 0.26 MiB | C++ |
 Dijkstra |
100 | 0.002 s | 0.28 MiB | C++ |
 超级傲娇的AC酱 |
100 | 0.002 s | 0.29 MiB | C++ |
 Extreme°/极致 ° |
100 | 0.002 s | 0.29 MiB | C++ |
 Dream |
100 | 0.002 s | 0.29 MiB | C++ |
| 本题关联比赛 | |||
| 20120316 | |||
| 关于 数字填充 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
这是一个极为有趣的证明。
嗯，。。刚刚我妈打电话把我批了一顿，大半夜了还不回家。。我先给个简述吧； 易证填数存在贪心规则，Max应和Min在一起。依次排序。[否则存在num>Min,num+Max>Min+Max] 填数应从对角线开始,以S型向对面填充{贪心规则可证Num1+1+Num2<Num1+Num2+n+1,Num1+Num2+2n+1=Num1+n+Num2+n+1}。可以发现式子中的对称性[Right1+Right2=Left1+Left2等价于Right1+Right2+1=Right1-n-1+Right2+n(同时满足Max填充和Min填充)]和层次[S型填充{贪心}]都会表现出来。 最大值出现在中心区域附近， 加之对称性，可得 Ans=Max-(2n+1)(int)/2+Min+n/2=Max+Min+n/2=N*N+N/2+1 介于直接证出来了，所以我就没有按照习惯测试各种算法的效率。但是还是大致说一下： 枚举O(n!) DP?这。。思路不是很清＝＝想过某种空间爆表的记忆化搜索。 贪心O(n^2) 数学证明O(1) 超级傲娇的AC酱
2013-12-01 09:42
2楼
| ||||
|
求大神证明过程
 Strawberry
2013-11-28 15:35
1楼
| ||||
【问题描述】
FireDancer最近迷上了一个填数的游戏：一个n*n的正方形棋盘，要把从1到n^2的整数填入到这个棋盘的每一个格子里(随意)。玩了很多次后，FireDancer发现了很多有趣的性质，他现在想考考你。他希望你得到一种棋盘的填法，使得任意相邻的两个格子里的数相加的最大值最小。这里的相邻指的是四个方向上的有公共边的相邻，而不是八个方向上的相邻。
【输入文件】
一个整数n(2<=n<=50)。(30％的数据n<=10)
【输出文件】
一个整数，为最小的那个值。
【输入样例】
2
【输出样例】
6
【样例说明】
一种最优填数方案为
1 4
3 2
此时，所有相邻的格子中4+2的和最大，为6。
若按以下方法填数
1 3
2 4
则，4+3的和最大，为7，没有6来得优。