PKU 1160 Post Office
1
/**//*
2
* File: 1160.cpp
3
* Author: GongZhi
4
* Problem: 動態規劃 四邊形優化
5
* Created on 2009年7月27日, 上午12:00
6
*/
7
8
#include <stdlib.h>
9
#include <string.h>
10
#include <iostream>
11
#include <string>
12
#include <vector>
13
#include <map>
14
#include <queue>
15
using namespace std;
16
17
/**//*
18
*
19
*/
20
#define MAXN 2000
21
int a[MAXN], sum[MAXN], f[MAXN][MAXN], w[MAXN][MAXN], p[MAXN][MAXN];
22
23
int main()
{
24
int n, m, i, j, t, k;
25
scanf("%d%d", &n, &m);
26
for (i = 1; i <= n; i++)scanf("%d", &a[i]);
27
sum[0] = 0;
28
for (i = 1; i <= n; i++)sum[i] = sum[i - 1] + a[i];
29
for (i = 1; i <= n; i++)
30
for (j = 1; j <= n; j++)
{
31
t = (i + j) / 2;
32
w[i][j] = (t - i + 1) * a[t]-(sum[t] - sum[i - 1]) +(sum[j] - sum[t - 1])-(j - t + 1) * a[t];
33
}
34
for (i = 1; i <= n; i++)
{
35
f[1][i] = w[1][i];
36
p[1][i] = 1;
37
}
38
for (i = 2; i <= m; i++)
{
39
j = n;
40
f[i][j] = 1000000000;
41
for (k = p[i - 1][j]; k <= j - 1; k++)
42
if (f[i - 1][k] + w[k + 1][j] < f[i][j])
{
43
f[i][j] = f[i - 1][k] + w[k + 1][j];
44
p[i][j] = k;
45
}
46
for (j = n - 1; j >= 1; j--)
{
47
f[i][j] = 1000000000;
48
for (k = p[i - 1][j]; k <= p[i][j+1]; k++)
49
if (f[i - 1][k] + w[k + 1][j] < f[i][j])
{
50
f[i][j] = f[i - 1][k] + w[k + 1][j];
51
p[i][j] = k;
52
}
53
}
54
}
55
printf("%d\n",f[m][n]);
56
return 0;
57
}
58
59
60

/**//* 2
* File: 1160.cpp3
* Author: GongZhi4
* Problem: 動態規劃 四邊形優化5
* Created on 2009年7月27日, 上午12:006
*/7

8
#include <stdlib.h>9
#include <string.h>10
#include <iostream>11
#include <string>12
#include <vector>13
#include <map>14
#include <queue>15
using namespace std;16

17

/**//*18
*19
*/20
#define MAXN 200021
int a[MAXN], sum[MAXN], f[MAXN][MAXN], w[MAXN][MAXN], p[MAXN][MAXN];22

23

int main()
{24
int n, m, i, j, t, k;25
scanf("%d%d", &n, &m);26
for (i = 1; i <= n; i++)scanf("%d", &a[i]);27
sum[0] = 0;28
for (i = 1; i <= n; i++)sum[i] = sum[i - 1] + a[i];29
for (i = 1; i <= n; i++)30

for (j = 1; j <= n; j++)
{31
t = (i + j) / 2;32
w[i][j] = (t - i + 1) * a[t]-(sum[t] - sum[i - 1]) +(sum[j] - sum[t - 1])-(j - t + 1) * a[t];33
}34

for (i = 1; i <= n; i++)
{35
f[1][i] = w[1][i];36
p[1][i] = 1;37
}38

for (i = 2; i <= m; i++)
{39
j = n;40
f[i][j] = 1000000000;41
for (k = p[i - 1][j]; k <= j - 1; k++)42

if (f[i - 1][k] + w[k + 1][j] < f[i][j])
{43
f[i][j] = f[i - 1][k] + w[k + 1][j];44
p[i][j] = k;45
}46

for (j = n - 1; j >= 1; j--)
{47
f[i][j] = 1000000000;48
for (k = p[i - 1][j]; k <= p[i][j+1]; k++)49

if (f[i - 1][k] + w[k + 1][j] < f[i][j])
{50
f[i][j] = f[i - 1][k] + w[k + 1][j];51
p[i][j] = k;52
}53
}54
}55
printf("%d\n",f[m][n]);56
return 0;57
}58

59

60


