学步园

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

#include <iostream><br /> using namespace std;<br /> typedef struct Cut<br /> {<br /> int startx ;<br /> int endx ;<br /> int starty ;<br /> int endy ;<br /> }Cut;<br /> // F of special matrix<br /> int computeF(int **array, int startx, int endx, int starty, int endy)<br /> {<br /> int i , j , k , l;<br /> int sum = 0 ;<br /> if ( startx + 1 >= endx && starty + 1 >= endy )<br /> {<br /> return 0 ;<br /> }<br /> for ( i = startx ; i < endx ; i ++ )<br /> {<br /> for ( j = starty ; j < endy ; j ++ )<br /> {<br /> for ( k = startx ; k < endx ; k ++ )<br /> {<br /> for ( l = starty ; l < endy ; l ++ )<br /> {<br /> if ( i < k || ( i == k && j < l ) )<br /> {<br /> sum += array[i][j] * array[k][l];<br /> }<br /> }<br /> }<br /> }<br /> }<br /> //return F ;<br /> return sum ;<br /> }<br /> int papercut(int **array, int maxF, int k, int current, Cut *c)<br /> {<br /> int i , j ;<br /> int minF = maxF ;<br /> int tempF ;<br /> int sumF = 0 ;<br /> Cut tempC;<br /> //切割完毕，计算F<br /> if ( current == k)<br /> {<br /> //loop for stack<br /> for ( i = 0 ; i < k + 1 ; i ++ )<br /> {<br /> sumF += computeF(array, c[i].startx, c[i].endx, c[i].starty, c[i].endy);<br /> }<br /> return sumF ;<br /> }<br /> //切割一次,统计下层,恢复栈状态<br /> //loop for stack<br /> for ( i = 0 ; i < current + 1 ; i ++ )<br /> {<br /> //temporal save<br /> tempC.startx = c[i].startx ;<br /> tempC.endx = c[i].endx ;<br /> tempC.starty = c[i].starty ;<br /> tempC.endy = c[i].endy ;<br /> //loop 行分割线<br /> for ( j = tempC.startx + 1 ; j < tempC.endx ; j ++ )<br /> {<br /> //替换当前栈元素为切割后的其中一块<br /> c[i].endx = j ; //<br /> //栈尾<br /> c[current + 1].startx = j ;<br /> c[current + 1].endx = tempC.endx ;<br /> c[current + 1].starty = tempC.starty ;<br /> c[current + 1].endy = tempC.endy ;<br /> tempF = papercut(array, maxF, k, current + 1, c) ;<br /> //复原当前栈元素<br /> c[i].endx = tempC.endx ;<br /> //<br /> if ( tempF < minF )<br /> {<br /> minF = tempF ;<br /> }<br /> }<br /> for ( j = tempC.starty + 1 ; j < tempC.endy ; j ++ )<br /> {<br /> //替换当前栈元素为切割后的其中一块<br /> c[i].endy = j ; //<br /> //栈尾<br /> c[current + 1].startx = tempC.startx ;<br /> c[current + 1].endx = tempC.endx ;<br /> c[current + 1].starty = j ;<br /> c[current + 1].endy = tempC.endy ;<br /> tempF = papercut(array, maxF, k, current + 1, c) ;<br /> //复原当前栈元素<br /> c[i].endy = tempC.endy ;<br /> //<br /> if ( tempF < minF )<br /> {<br /> minF = tempF ;<br /> }<br /> }<br /> }<br /> return minF ;<br /> }<br /> int main()<br /> {<br /> int **array ;<br /> int i , j ;//loop variables<br /> int N , M , k ; //<br /> int minF, maxF ;<br /> Cut *c ; // used as a stack<br /> //input and ask for memory<br /> cin >> N ;<br /> cin >> M ;<br /> cin >> k ;<br /> array = new int*[N] ;<br /> for ( i = 0 ; i < N ; i ++ )<br /> {<br /> array[i] = new int[M] ;<br /> }<br /> for ( i = 0 ; i < N ; i ++ )<br /> {<br /> for ( j = 0 ; j < M ; j ++ )<br /> {<br /> cin >> array[i][j] ;<br /> }<br /> }<br /> c = new Cut[k+1] ;<br /> //k too big<br /> if ( k >= (M-1)+M*(N-1) )<br /> {<br /> cout << "0" << endl ;<br /> return 0;<br /> }<br /> //procedure and optimize<br /> c[0].startx = 0 ;<br /> c[0].endx = N ;<br /> c[0].starty = 0 ;<br /> c[0].endy = M ;<br /> maxF = computeF(array, 0, N, 0, M);//初始矩形的F值<br /> minF = papercut(array, maxF, k, 0, c) ;<br /> cout << minF << endl ;<br /> return 0 ;<br /> }