UESTC 594 我要长高
韩父有.请你帮助韩父让韩家损失最小。
Input
有若干组数据，一直处理到文件结束。
每组数据第一行为两个整数：韩子数量)
接下来)。
Output
对每组测试数据用一行输出韩家的最小损失。
Sample Input
5 2 2 3 5 1 4
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 0x3fffffff 13 #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 else 48 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 ", 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 0x3fffffff 13 #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 else 45 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 ", res); 58 } 59 60 int main() { 61 while(init()) { 62 solve(); 63 } 64 return 0; 65 }