斜率优化DP – hahaschool

HDU 3669 Cross the Wall

August 02, 20152015-08-02hahaschoolLeave a comment

题意

思路

需要一定的转化的斜率优化DP。

代码

//
//  HDU3669.cpp
//  playground
//
//  Created by Adam Chang on 2015/08/02.
//  Copyright © 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

vector<pair<long long, long long> > tmp_block;
vector<pair<long long, long long> > block;
bool cmp(pair<long long, long long> a,pair<long long, long long> b){
    if (a.first != b.first) {
        return a.first < b.first;
    }
    return a.second > b.second;
}
const int maxn = 50005;
const long long maxll = 0x3f3f3f3f3f3f3f3f;
long long dp[2][maxn];
int que[maxn];
int head = 0,tail = 0;

long long slope_upper(int t,int a,int b){
    return dp[(t-1)%2][a] - dp[(t-1)%2][b];
}

long long slope_lower(int a,int b){
    return block[b].second - block[a].second;
}

long long get_dp(int t,int i,int h){
    return dp[(t-1)%2][que[h]] + block[i-1].first * block[que[h]].second;
}
int main(){
    long long n = 0,k = 0;
    while (scanf(" %lld %lld",&n,&k) != EOF) {
        memset(dp[0], 0x3f, sizeof(dp[0]));
        dp[0][0] = 0;
        tmp_block.clear();
        block.clear();
        for (int i = 1; i <= n; i++) {
            long long w = 0,h = 0;
            scanf(" %lld %lld",&w,&h);
            tmp_block.push_back(make_pair(h, w));
        }
        sort(tmp_block.begin(), tmp_block.end(), cmp);
        long long curmin = maxll;
        for (int i = 1; i <= n ; i++) {
            if (tmp_block[i-1].second <= curmin) {
                block.push_back(tmp_block[i-1]);
            }
            curmin = tmp_block[i-1].second;
        }
        n = block.size();
        block.push_back(make_pair(0, 0));
        long long res = maxll;
        for (int t = 1; t <= k; t++) {
            head = tail = 0;
            que[tail++] = t-1;
            for (int i = t; i <= n; i++) {
                while (head + 1 < tail
                       && slope_upper(t, que[head + 1], que[head]) <= block[i-1].first * slope_lower(que[head + 1], que[head])) {
                    head++;
                }
                dp[t%2][i] = get_dp(t, i, head);
                while (head + 1 < tail
                       && slope_upper(t, que[tail - 2], que[tail - 1]) * slope_lower(que[tail - 1], i) >= slope_lower(que[tail - 2], que[tail - 1]) * slope_upper(t, que[tail - 1], i)) {
                    tail--;
                }
                que[tail++] = i;
            }
            res = min(res, dp[t%2][n]);
        }
        cout << res << endl;
    }

    return 0;
}

// HDU3669.cpp

// playground

// Created by Adam Chang on 2015/08/02.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

vector<pair<long long, long long> > tmp_block;

vector<pair<long long, long long> > block;

bool cmp(pair<long long, long long> a,pair<long long, long long> b){

if (a.first != b.first) {

return a.first < b.first;

}

return a.second > b.second;

}

const int maxn = 50005;

const long long maxll = 0x3f3f3f3f3f3f3f3f;

long long dp[2][maxn];

int que[maxn];

int head = 0,tail = 0;

long long slope_upper(int t,int a,int b){

return dp[(t-1)%2][a] - dp[(t-1)%2][b];

}

long long slope_lower(int a,int b){

return block[b].second - block[a].second;

}

long long get_dp(int t,int i,int h){

return dp[(t-1)%2][que[h]] + block[i-1].first * block[que[h]].second;

}

int main(){

long long n = 0,k = 0;

while (scanf(" %lld %lld",&n,&k) != EOF) {

memset(dp[0], 0x3f, sizeof(dp[0]));

dp[0][0] = 0;

tmp_block.clear();

block.clear();

for (int i = 1; i <= n; i++) {

long long w = 0,h = 0;

scanf(" %lld %lld",&w,&h);

tmp_block.push_back(make_pair(h, w));

}

sort(tmp_block.begin(), tmp_block.end(), cmp);

long long curmin = maxll;

for (int i = 1; i <= n ; i++) {

if (tmp_block[i-1].second <= curmin) {

block.push_back(tmp_block[i-1]);

}

curmin = tmp_block[i-1].second;

}

n = block.size();

block.push_back(make_pair(0, 0));

long long res = maxll;

for (int t = 1; t <= k; t++) {

head = tail = 0;

que[tail++] = t-1;

for (int i = t; i <= n; i++) {

while (head + 1 < tail

&& slope_upper(t, que[head + 1], que[head]) <= block[i-1].first * slope_lower(que[head + 1], que[head])) {

head++;

}

dp[t%2][i] = get_dp(t, i, head);

while (head + 1 < tail

&& slope_upper(t, que[tail - 2], que[tail - 1]) * slope_lower(que[tail - 1], i) >= slope_lower(que[tail - 2], que[tail - 1]) * slope_upper(t, que[tail - 1], i)) {

tail--;

}

que[tail++] = i;

}

res = min(res, dp[t%2][n]);

}

cout << res << endl;

}

return 0;

}

HDU 2829 Lawrence

August 01, 20152015-08-01hahaschoolLeave a comment

题意

本题和HDU 3507 Print Article如出一辙。都是给出了一个数列，和一个费用公式，要你设计一种把数列分为若干组之后计算出的总费用达到最小的方案。

思路

依然是斜率优化DP。不过本题有两个要点必须注意：1.我们默认炸毁了某一道路之后，就不要再去管默许炸毁了的道路之前的节点了。2.一定要注意DP数组的正确初始化（因为这个我挑通宵调试了近10小时）。

详细的状态转移方程还是建议自己推导，因为下标等微妙的细节稍有相左，就会产生错误，如果确信自己的方程没有问题不妨从上面几个要点调试。如果没有掌握斜率优化DP的基本知识，请移步HDU 3507 Print Article并仔细阅读教程。

代码

//
//  HDU2829.cpp
//  playground
//
//  Created by Adam Chang on 2015/08/01.
//  Copyright © 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

const long long maxn = 1010;
long long n, m;
long long a[maxn], sum[maxn], sumul[maxn];
long long dp[2][maxn];
long long que[maxn], head, tail;

long long slope_upper(long long l, long long b, long long a)
{
    return (dp[l%2][a] - sumul[a] + sum[a] * sum[a]) - (dp[l%2][b] - sumul[b] + sum[b] * sum[b]);
}

long long slope_lower(long long b, long long a)
{
    return sum[a] - sum[b];
}

int main()

{
    //freopen("testdata.hdub", "r", stdin);
    while (scanf("%lld%lld", &n, &m) != EOF) {
        if (n == 0 && m == 0) break;
        sum[0] = 0;
        sumul[0] = 0;
        for (long long i = 1; i <= n; ++i) {
            scanf("%lld", &a[i]);
            sum[i] = sum[i-1] + a[i];
            sumul[i] = sumul[i-1] + sum[i-1] * a[i];
            dp[0][i] = sumul[i];
        }
        for (long long i = 1; i <= m; ++i) {
            head = tail = 0;
            que[tail++] = i;
            for (long long j = i+1; j <= n; ++j) {
                while (head + 1 < tail && slope_upper(i-1, que[head], que[head+1]) <= sum[j] * slope_lower(que[head], que[head+1])) {
                    head++;
                }
                dp[i%2][j] = dp[(i-1)%2][que[head]] + sumul[j] - sumul[que[head]] - sum[que[head]] * (sum[j] - sum[que[head]]);
                while (head + 1 < tail && slope_upper(i - 1, que[tail-2], que[tail-1]) * slope_lower(que[tail-1], j) >= slope_lower(que[tail-2], que[tail-1]) * slope_upper(i - 1, que[tail-1], j)) {
                    tail--;
                }
                que[tail++] = j;
            }
        }
        printf("%lld\n", dp[m%2][n]);
    }
    return 0;
}

// HDU2829.cpp

// playground

// Created by Adam Chang on 2015/08/01.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

const long long maxn = 1010;

long long n, m;

long long a[maxn], sum[maxn], sumul[maxn];

long long dp[2][maxn];

long long que[maxn], head, tail;

long long slope_upper(long long l, long long b, long long a)

{

return (dp[l%2][a] - sumul[a] + sum[a] * sum[a]) - (dp[l%2][b] - sumul[b] + sum[b] * sum[b]);

}

long long slope_lower(long long b, long long a)

{

return sum[a] - sum[b];

}

int main()

{

//freopen("testdata.hdub", "r", stdin);

while (scanf("%lld%lld", &n, &m) != EOF) {

if (n == 0 && m == 0) break;

sum[0] = 0;

sumul[0] = 0;

for (long long i = 1; i <= n; ++i) {

scanf("%lld", &a[i]);

sum[i] = sum[i-1] + a[i];

sumul[i] = sumul[i-1] + sum[i-1] * a[i];

dp[0][i] = sumul[i];

}

for (long long i = 1; i <= m; ++i) {

head = tail = 0;

que[tail++] = i;

for (long long j = i+1; j <= n; ++j) {

while (head + 1 < tail && slope_upper(i-1, que[head], que[head+1]) <= sum[j] * slope_lower(que[head], que[head+1])) {

head++;

}

dp[i%2][j] = dp[(i-1)%2][que[head]] + sumul[j] - sumul[que[head]] - sum[que[head]] * (sum[j] - sum[que[head]]);

while (head + 1 < tail && slope_upper(i - 1, que[tail-2], que[tail-1]) * slope_lower(que[tail-1], j) >= slope_lower(que[tail-2], que[tail-1]) * slope_upper(i - 1, que[tail-1], j)) {

tail--;

}

que[tail++] = j;

}

printf("%lld\n", dp[m%2][n]);

}

return 0;

}

HDU 3507 Print Article

July 31, 20152015-07-31hahaschoolOne Comment

题意

给出了一个费用计算公式，现在要你把一个数列分成若干组，每一组分别套用给出的费用计算公式计算费用。你要设计一种方法使得总费用最小。

思路

本题的DP方程推导相对容易（不过我学艺不精被卡在了这一步），之后我们会发现导出的方程完全无法满足时间限制，这个时候通过对费用公式的变形可以导出一种适用于斜率优化DP的形式。

斜率优化的操作非常复杂，幸运的是已经有人写出了详实的教程：斜率优化DP。这篇教程基本是斜率优化教程中最好理解的了，并且以这个题为例题。建议学习时手动模拟操作过程，以便形象、深入地理解。

代码

实现斜率优化的要点：1.合理正确地推导出斜率的表示形式和所有的转移方程、决策判定条件。2.正确地选择大于小于号。3.单调队列的实现，同时注意单调队列无法使用STL很好地实现，只能数组模拟。4.正确地初始化DP数组（非常重要）。

//
//  HDU3507.cpp
//  playground
//
//  Created by Adam Chang on 2015/07/30.
//  Copyright © 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

#define MAXN 500000 + 10

long long sum[MAXN];
long long dp[MAXN];
int que[MAXN];

long long slope_upper(int a,int b){
    return (dp[a] + sum[a] * sum[a]) - (dp[b] + sum[b] * sum[b]);
}

long long slope_lower(int a,int b){
    return 2 * (sum[a] - sum[b]);
}

int main(){
    long long n = 0, m = 0;
    while (scanf(" %lld %lld",&n,&m) != EOF) {
        int head = 0, tail = 0;
        que[tail++] = 0;
        for (int i = 1; i <= n; i++) {
            scanf(" %lld",&sum[i]);
            sum[i] += sum[i-1];
            while (head + 1 < tail && slope_upper(que[head + 1], que[head]) <= sum[i] * slope_lower(que[head + 1], que[head])) {
                head++;
            }
            dp[i] = dp[que[head]] + m + (sum[i] - sum[que[head]]) * (sum[i] - sum[que[head]]);
            while (head + 1 < tail && slope_upper(i, que[tail - 1]) * slope_lower(que[tail - 1], que[tail - 2]) <= slope_upper(que[tail - 1], que[tail - 2]) * slope_lower(i, que[tail - 1])) {
                tail--;
            }
            que[tail++] = i;
        }
        printf("%lld\n",dp[n]);
    }

    return 0;
}

// HDU3507.cpp

// playground

// Created by Adam Chang on 2015/07/30.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

#define MAXN 500000 + 10

long long sum[MAXN];

long long dp[MAXN];

int que[MAXN];

long long slope_upper(int a,int b){

return (dp[a] + sum[a] * sum[a]) - (dp[b] + sum[b] * sum[b]);

}

long long slope_lower(int a,int b){

return 2 * (sum[a] - sum[b]);

}

int main(){

long long n = 0, m = 0;

while (scanf(" %lld %lld",&n,&m) != EOF) {

int head = 0, tail = 0;

que[tail++] = 0;

for (int i = 1; i <= n; i++) {

scanf(" %lld",&sum[i]);

sum[i] += sum[i-1];

while (head + 1 < tail && slope_upper(que[head + 1], que[head]) <= sum[i] * slope_lower(que[head + 1], que[head])) {

head++;

}

dp[i] = dp[que[head]] + m + (sum[i] - sum[que[head]]) * (sum[i] - sum[que[head]]);

while (head + 1 < tail && slope_upper(i, que[tail - 1]) * slope_lower(que[tail - 1], que[tail - 2]) <= slope_upper(que[tail - 1], que[tail - 2]) * slope_lower(i, que[tail - 1])) {

tail--;

}

que[tail++] = i;

}

printf("%lld\n",dp[n]);

}

return 0;

}