首页 > 代码库 > POJ 3709 K-Anonymous Sequence 斜率优化
POJ 3709 K-Anonymous Sequence 斜率优化
容易得出简单的递推方程如下
f[i] = min{f[j] + sum[i] - sum[j] - (i-j) *x[j+1] }
然后发现复杂度太高
这时可以看出是一个比较经典的斜率优化
f[i] = min{f[j] +j *x[j+1] -sum[j] -i *x[j+1]} +sum[i]
按照http://blog.csdn.net/sdj222555/article/details/8229192 中使用的斜率优化方法推导就行了
可以发现一些单调性是比较重要的
最后需要注意的由于有k这个条件的限制
所以某个决策点要入队的时候,需要延迟入队。
就是说走完 i 这个点的时候,把下一个点即(i+1)可能用到的状态加入队列,就是i-k+1
如代码所示
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #define INF 1011111111 #define eps 1e-12 #define MAXN 555555 #define MAXM 55555 using namespace std; int n, k; long long f[MAXN], x[MAXN], sum[MAXN]; int q[MAXN]; long long g(int j) { return f[j] + (long long)j * x[j] - sum[j]; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &k); for(int i = 0; i < n; i++) x[i] = in(); sum[0] = 0; for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + x[i - 1]; int l = 1, r = 1; q[1] = 0; f[0] = 0; for(int i = 1; i <= n; i++) { while(q[l] + 2 * k <= i) l++; while(l < r && (long long)i * (x[q[l + 1]] - x[q[l]]) >= g(q[l + 1]) - g(q[l])) l++; f[i] = f[q[l]] + x[q[l]] * (long long)(q[l] - i) + sum[i] - sum[q[l]]; if(i - k + 1 >= k) { while(l < r && (g(q[r]) - g(q[r - 1])) * (x[i - k + 1] - x[q[r]]) >= ((g(i - k + 1) - g(q[r])) * (x[q[r]] - x[q[r - 1]]))) r--; q[++r] = i - k + 1; } } printf("%I64d\n", f[n]); } return 0; }
POJ 3709 K-Anonymous Sequence 斜率优化
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。