2009腾讯创新大赛 题五

[higer]

Papercut
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 198 Accepted: 68

Description

现在桌面上有一张矩形纸，上边有n×m个格子，每个格子有一个数字。 每张矩形纸可以算出一个数值F，F是由纸张里任意两个不同的格子里的数字相乘之
和。如果该纸只有一个格子，那么F=0。

剪纸规则是：
1、沿格子边缘一直剪成两个矩形纸，每张纸里必须有数字。
2、每次剪纸在桌面上任意选一张矩形纸，进行1操作，再把剪出来的两张纸放到桌面。

现在你可以对桌面上的纸最多剪k次，问最后桌面上所有矩形纸的F值之和最小是多少？

1 ≤ n ≤ 10
1 ≤ m ≤ 10
1 ≤ k ≤ 50

Input

第一行：3个整数n, m, k
接下来n行：每行m个正整数，范围在[1,10]，第i行第j个数表示当前桌面那张矩形纸里边第i行第j个格子里的数字。

Output

一个整数。代表最小F值和。
Sample Input

Sample Input #1
4 4 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Sample Input #2
10 10 5
4 2 3 5 6 10 1 6 5 8
3 6 9 1 7 10 7 10 8 1
7 8 3 3 2 5 9 9 8 2
5 5 9 9 3 10 2 9 10 2
1 1 6 7 6 8 3 9 6 8
7 1 2 5 3 2 3 7 8 10
10 9 8 9 7 8 10 7 3 9
6 3 6 2 1 7 10 6 7 2
2 4 8 4 5 9 10 5 9 10
7 4 3 2 4 9 9 9 8 1

Sample Output

Sample Output #1
18
Sample Output #2
26612

Hint

Sample 1说明： 按照下面方式剪纸4次
1 1 1 1
-------------
1 | 1 | 1 | 1
| | |
1 | 1 | 1 | 1
| | |
1 | 1 | 1 | 1
得到6+3+3+3+3=18

[nobody]

对n*m的矩阵，如果在i行横着切,则产生两个矩阵 i*m, (n-i)*m. 这样就有了一堆规模更小的子问题。
矩阵i*m,(n-i)*m,分别对其切.然后求和最小的切法即可。

用函数 solve(i1,j1,i2,j2,k)表示矩形(i1,j1,i2,j2)切k次所得到的最小F值。

不切的时候，即k==0的时候，f值等于(和的平方减去平方和)/2。这个用平方和公式很容易推导。

则 solve(i1,j1,i2,j2,k) = min{

//横着切
for i = i1...i2-1
for t = 0...k-1
//上边切t刀，下边切k-1-t刀。
min solve(i1,j1,i,j2,t)+solve(i+1,j1,i2,j2,k-1-t);

//竖着切，类似，略。
}

求 solve(1,1,n,m,k)即可。

这个是递归公式，动态规划递推写出来即可。时间复杂度为O(k*n*m*n*m*(m+n)*k)
最大计算次数为(5*10^8)

递推可能会超时....memoization的方式应该能过.
程序就不贴了...

[higer]

这个题感觉很难，当时都不知道怎么下手。
现在做了怎么知道自己做的是对的还是错的呢？

[nobody]

可以做做poj　1191题
类似的，棋盘分割问题．

On 5月24日, 下午5时48分, higer <higerinbeij...@gmail.com> wrote:
> 这个题感觉很难，当时都不知道怎么下手。
> 现在做了怎么知道自己做的是对的还是错的呢？
>