您现在的位置是：主页 > news > 厦门网站建设是什么意思/杨谦教授编的营销课程

厦门网站建设是什么意思/杨谦教授编的营销课程

admin2025/5/15 9:05:59【news】

简介厦门网站建设是什么意思,杨谦教授编的营销课程,ip反查域名在线工具,创造一个软件需要多少钱动态规划需要用数据结构优化的动态规划 poj2754,poj3378,poj3017 四边形不等式理论、斜率优化 poj1160，poj1180，poj3709 较难的状态DP、插头DP poj3133,poj1739,poj2411、poj1763 需要用数据结构优化的动态规划 POJ 3017 题意：给一个长…

厦门网站建设是什么意思,杨谦教授编的营销课程,ip反查域名在线工具,创造一个软件需要多少钱动态规划需要用数据结构优化的动态规划 poj2754,poj3378,poj3017 四边形不等式理论、斜率优化 poj1160，poj1180，poj3709 较难的状态DP、插头DP poj3133,poj1739,poj2411、poj1763 需要用数据结构优化的动态规划 POJ 3017 题意：给一个长…

动态规划	需要用数据结构优化的动态规划	poj2754,poj3378,poj3017
	四边形不等式理论、斜率优化	poj1160，poj1180，poj3709
	较难的状态DP、插头DP	poj3133,poj1739,poj2411、poj1763

需要用数据结构优化的动态规划

POJ 3017

　题意：给一个长为N的序列A，从中可以画出k个子序列，S1，S2，... ，Sk。求这些子序列中sigma(max(S[i]))最小。（1<=i<=k）并且满足sigma(S[i])<= M;

解：转移方程，f[i] = min(f[j] + max(num[j+1...i]))，这是一个很朴素的O(N^2)的复杂度。需要优化。

可以发现，对于f[], 如果j < i那么f[j] <= f[i]。所以f[i]是单调的，要取最小首先考虑j足够小的问题，但是num[j+1...i]这一段就没有大小序列了。怎么办，直接开单调队列，保存一个从大到小的队列。计算结果的时候直接从队头取元素转移，即：f[i] = f[q[head]-1] + num[q[head]](这里队列记录的是数的下标)。这还不一定能满足所有的情况

比如序列4 5 3, M = 9

f[1] = 4, f[2] = 5, f[3] = 8;

但如果单纯的f[i] = f[q[head]-1] + num[q[head]]，f[3] = f[1] + num[2] = 9;

其实f[i]的最优解在f[i] = min(f[q[i-1]] + num[q[i]]);即根据单调队列里面相邻的两个元素进行转移。

View Code

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>using namespace std;typedef long long LL;const int N = 100020;LL num[N];
LL sum[N];
LL f[N];
int q[N];int main() {//freopen("data.in", "r", stdin);int n, i, j, st, ed, p;//bool fg;
    LL m;while(~scanf("%d%I64d", &n, &m)) {memset(f, -1, sizeof(f));st = 0, ed = -1;p = 1;sum[0] = 0;f[0] = 0;//fg = true;for(i = 1; i <= n; ++i) {scanf("%I64d", num + i);//if(num[i] > m)  fg = false;sum[i] = sum[i-1] + num[i];if(st > ed) {st = 0, ed = -1;q[++ed] = i;}while(st <= ed && num[i] >= num[q[ed]])   --ed;q[++ed] = i;while(sum[i] - sum[p-1] > m)    ++p;while(st <= ed && p > q[st])    st++;if(st > ed) continue;if(f[p-1] != -1)f[i] = f[p-1] + num[q[st]];for(j = st + 1; j <= ed; ++j) {if(f[q[j]-1] != -1)f[i] = min(f[i], f[q[j-1]] + num[q[j]]);}}printf("%I64d\n",f[n]);}return 0;
}