vinoМеня заинтересовал именно код в 20 строк, таких решений я еще не встречал, но интересно
retty_jj_007blaka zakata,
если код (там 20 строк) еще нужен дай знать
прошу прощения, vino, я был чудовищно невежлив. Вот код:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
int tcs, n, m, p, w, h;
int a[ 605 ][ 605 ];
int main() {
//freopen("E:\\C++\\SPOJ\\TestData\\88.txt", "rt", stdin);
//freopen("E:\\C++\\SPOJ\\TestData\\99.txt", "wt", stdout);
scanf("%d", &tcs);
while (tcs-- > 0) {
scanf("%d %d", &m, &n);
for (int i = 0 ; i <= n; ++i)
for (int j = 0 ; j <= m; ++j)
a[i][j] = i * j;
scanf("%d", &p);
for (int i = 1 ; i <= p; ++i) {
scanf("%d %d", &w, &h);
////a[w][h] = 0 ;
a[h][w] = 0 ;
}
for (int x = 1 ; x <= n; ++x) {
for (int y = 1 ; y <= m; ++y) {
for (int c = 1 ; c < y; ++c)
a[x][y] = min(a[x][y], a[x][c] + a[x][y - c]);
for (int c = 1 ; c < x; ++c)
a[x][y] = min(a[x][y], a[c][y] + a[x - c][y]);
}
}
printf("%d\n", a[n][m]);
}
return 0 ;
}
это под эту задачу:
http://www.spoj.pl/problems/PHIDIAS/
