【区间dp】P1220 关路灯

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int pos[51];
 7 int w[51];
 8 int sum[51][51];
 9 int f[51][51][2];
10 
11 int main()
12 {
13     int n, c;
14     cin >> n >> c;
15     for (int i = 1; i <= n; i++)
16     {
17         cin >> pos[i];
18         cin >> w[i];
19     }
20     for (int i = 1; i <= n; i++)
21     {
22         sum[i][i] = w[i];
23         for (int j = i + 1; j <= n; j++)
24         {
25             sum[i][j] = sum[i][j - 1] + w[j];
26         }
27     }
28     memset(f, 0x3f, sizeof(f));
29     f[c][c][0] = 0;
30     f[c][c][1] = 0;
31     for (int i = 2; i <= n; i++)
32         for (int j = 1; i + j - 1 <= n; j++)
33         {
34             int l = j;
35             int r = i + j - 1;
36             f[l][r][0] = min(f[l + 1][r][0] + (pos[l+1] - pos[l]) * (sum[1][l] + sum[r + 1][n]), f[l + 1][r][1] + (pos[r] - pos[l]) * (sum[1][l] + sum[r + 1][n]));
37             f[l][r][1] = min(f[l][r - 1][0] + (pos[r] - pos[l]) * (sum[1][l - 1] + sum[r][n]), f[l][r - 1][1] + (pos[r] - pos[r-1]) * (sum[1][l - 1] + sum[r][n]));
38         }
39     cout << min(f[1][n][0], f[1][n][1]);
40 }