首页 > 代码库 > UESTC 594 我要长高 - 单调性优化

UESTC 594 我要长高 - 单调性优化

2024-09-19 19:28:52   205人阅读

　　韩父有N个儿子，分别是韩一，韩二…韩N。由于韩家演技功底深厚，加上他们间的密切配合，演出获得了巨大成功，票房甚至高达2000万。舟子是名很有威望的公知，可是他表面上两袖清风实则内心阴暗，看到韩家红红火火，嫉妒心遂起，便发微薄调侃韩二们站成一列时身高参差不齐。由于舟子的影响力，随口一句便会造成韩家的巨大损失，具体亏损是这样计算的，韩一，韩二…韩N站成一排，损失即为C×（韩i与韩i+1的高度差（1≤i<N））之和，搞不好连女儿都赔了.韩父苦苦思索，决定给韩子们内增高（注意韩子们变矮是不科学的只能增高或什么也不做），增高1cm是很容易的，可是增高10cm花费就很大了，对任意韩ii，增高Hcm的花费是H2.请你帮助韩父让韩家损失最小。

Input

有若干组数据，一直处理到文件结束。

每组数据第一行为两个整数：韩子数量N(1≤N≤50000)和舟子系数C(1≤C≤100)

接下来NN行分别是韩i的高度(1≤hi≤100)。

Output

对每组测试数据用一行输出韩家的最小损失。

Sample Input

5 223514

Sample Output

15

Hint

输入数据多请使用scanf代替cin

　　f[i][j]表示第i个人，高度为j的最小损失，显然

技术分享

　　然后乱搞一下，分类发讨论一下绝对值，把无关项都移出来，于是得到了

技术分享

　　接着跑两道单调队列优化就好了，总时间复杂度O(100n)，动态规划的空间复杂度如果开滚动数组就是O(200)

　　由于此题比较特殊，所以可以直接更新一个变量，单调队列都不用了。

Code

技术分享
 1 /** 2  * UESTC 3  * Problem#594 4  * Accepted 5  * Time:364ms 6  * Memory:1364k 7  */ 8 #include<iostream> 9 #include<cstdio>10 using namespace std;11 typedef bool boolean;12 #define inf 0x3fffffff13 #define smin(a, b) (a) = min((a), (b))14 #define smax(a, b) (a) = max((a), (b))15 16 int n, c;17 int *h;18 int t;19 int f[2][105];20 21 inline boolean init() {22     if(scanf("%d%d", &n, &c) == -1)    return false;23     h = new int[(const int)(n + 1)];24     for(int i = 1; i <= n; i++) {25         scanf("%d", h + i);26     }27     return true;28 }29 30 int q[105];31 int rear;32 inline void solve() {33     t = 0;34     for(int i = 0; i < h[1]; i++)35         f[t][i] = inf;36     for(int i = h[1]; i <= 100; i++)37         f[t][i] = (i - h[1]) * (i - h[1]);38     for(int i = 2; i <= n; i++) {39         t ^= 1;40         rear = 0;41         for(int j = 0; j <= 100; j++) {42             int val = f[t ^ 1][j] - j * c;43             while(rear && q[rear] > val)    rear--;44             q[++rear] = val;45             if(j < h[i])46                 f[t][j] = inf;47             else48                 f[t][j] = q[1] + j * c + (j - h[i]) * (j - h[i]);49         }50         rear = 0;51         for(int j = 100; j >= h[i]; j--) {52             int val = f[t ^ 1][j] + j * c;53             while(rear && q[rear] > val)    rear--;54             q[++rear] = val;55             smin(f[t][j], q[1] - j * c + (j - h[i]) * (j - h[i]));56         }57     }58     int res = inf;59     for(int i = 0; i <= 100; i++)60         smin(res, f[t][i]);61     printf("%d\n", res);62     delete[] h;63 }64 65 int main() {66     while(init()) {67         solve();68     }69     return 0;70 }
类似单调队列的代码

Code(常数优化后的代码)

 1 /** 2  * UESTC 3  * Problem#594 4  * Accepted 5  * Time:136ms 6  * Memory:1172k 7  */ 8 #include<iostream> 9 #include<cstdio>10 using namespace std;11 typedef bool boolean;12 #define inf 0x3fffffff13 #define smin(a, b) (a) = min((a), (b))14 #define smax(a, b) (a) = max((a), (b))15 16 int n, c;17 int t;18 int h[50005];19 int f[2][105];20 21 inline boolean init() {22     if(scanf("%d%d", &n, &c) == -1)    return false;23     for(int i = 1; i <= n; i++) {24         scanf("%d", h + i);25     }26     return true;27 }28 29 int cmp;30 inline void solve() {31     t = 0;32     for(int i = 0; i < h[1]; i++)33         f[t][i] = inf;34     for(int i = h[1]; i <= 100; i++)35         f[t][i] = (i - h[1]) * (i - h[1]);36     for(int i = 2; i <= n; i++) {37         t ^= 1;38         cmp = inf;39         for(int j = 0; j <= 100; j++) {40             int val = f[t ^ 1][j] - j * c;41             smin(cmp, val);42             if(j < h[i])43                 f[t][j] = inf;44             else45                 f[t][j] = cmp + j * c + (j - h[i]) * (j - h[i]);46         }47         cmp = inf;48         for(int j = 100; j >= h[i]; j--) {49             int val = f[t ^ 1][j] + j * c;50             smin(cmp, val);51             smin(f[t][j], cmp - j * c + (j - h[i]) * (j - h[i]));52         }53     }54     int res = inf;55     for(int i = 0; i <= 100; i++)56         smin(res, f[t][i]);57     printf("%d\n", res);58 }59 60 int main() {61     while(init()) {62         solve();63     }64     return 0;65 }

UESTC 594 我要长高 - 单调性优化


联系
我们