首页 > 代码库 > 福建省冬令营 Day2 T1

福建省冬令营 Day2 T1

技术分享

技术分享

技术分享


 题解:

技术分享

 

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cstdio>
 6 #include<cmath>
 7 using namespace std;
 8 inline void Scan(int &x)
 9 {
10     char c;
11     while((c = getchar()) < 0 || c > 9);
12     x = c - 0;
13     while((c = getchar()) >= 0 && c <= 9) x = x * 10 + c - 0;
14 }
15 const int me = 1000233;
16 int n;
17 int atk;
18 int a[me], b[me], h[me];
19 int f[523][523];
20 int main()
21 {
22     Scan(n);
23     Scan(atk);
24     for(int i = 1; i <= n; ++i)
25         Scan(a[i]), Scan(b[i]), Scan(h[i]);
26     for(int i = 1; i <= n; ++i)
27     {
28         int m = h[i] / atk;
29         if(h[i] % atk) ++m;
30     }
31     for(int l = 1; l <= n; ++l)
32         for(int i = 1; i <= n - l + 1; ++i)
33         {
34             int j = i + l - 1;
35             f[i][j] = 707406378;
36             for(int k = i; k <= j; ++k)
37             {
38                 int m = h[k] / atk;
39                 if(h[k] % atk) ++m;
40                 f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 1][j] + m * (a[k] + b[i - 1] + b[j + 1]));
41             }
42         }
43     printf("%d", f[1][n]);
44 }

福建省冬令营 Day2 T1