问题 2473. -- 扑克の阵

2473: 扑克の阵

时间限制: 0 Sec  内存限制: 128 MB
提交: 0  解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

在越过了第一道关卡之后，KID暂时摆脱了OIBH组织的追兵。基德为了不被打扰，决定送给OIBH组织一份大礼：那就是扑克阵法。基德的扑克阵法是扑克牌组成的N*N的大方阵，要解开这个阵法的要诀就是，拿走两个互不重叠的K*K的方阵中的扑克牌，使得这2*k^2张扑克牌的总分最大，从而使整个阵法失去主要能量而土崩瓦解。但是，基德自己在偷完回去的路上也会碰到这个阵法——为了不至于自己把自己困住——基德需要你帮助他编程解决这个阵法。

输入 [pkz.in]

第1行两个数n，k。
第2行到第n+1行，每行n个非负整数，表示整个扑克阵法每张牌的分值。

输出 [pkz.out]

一个数，表示最大能拿走的总分。

样例输入

4 2
1 1 1 1
8 8 1 1
8 8 9 9
1 1 9 9

样例输出

68

提示

对于20%的数据,1< =k< =n< =50
对于100%的数据,1< =k< =n< =1000
保证答案不超过2^31-1。

标签

普及一等 动态规划 怪盗基德-月下の谜 VIJOS

[上一题][提交][讨论版][状态][下一题]