首页 > 代码库 > 福建省冬令营 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。