A simple Blog for wyx I've been down the bottle hoping.
4884: [Lydsy2017年5月月赛]太空猫 dp
发表于: | 分类: Oi | 评论:0 | 阅读:67

首先容易发现向左走就是在骗你

然后就是傻逼dp

$f_{i,0/1}$表示到达$i$处的上/下面的最小代价

不会转移的左转NOIP普及组学习双线程dp

注意无解的情况

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
typedef long long LL;
const LL inf = 1e18;
const int N = 1e5+5;
using namespace std;
int n;
int a[N], b[N], c[N];
LL F[N][2];
inline void up(LL &x,LL y) {if(x > y) x = y;}
int main() {
    cin >> n;
    for(int i=1;i<=n;++i) scanf("%d", a+i);
    for(int i=1;i<=n;++i) scanf("%d", b+i), c[i] = a[i] - b[i];
    for(int i=2;i<=n;++i) {
        if(b[i] >= a[i-1] || b[i-1] >= a[i]) return 0 * puts("-1");
    }
    for(int i=1;i<=n;++i) F[i][0] = F[i][1] = inf;
    F[1][0] = 0;
    for(int i=1;i<=n;++i) {
        if(i > 1) {
            if(a[i-1] <= a[i]) up(F[i][1], F[i-1][1]);
            if(b[i-1] >= b[i]) up(F[i][0], F[i-1][0]);
        }
        up(F[i][0], F[i][1] + c[i]);
        up(F[i][1], F[i][0] + c[i]);
    }
    if(F[n][0] >= inf) F[n][0] = -1;
    cout << F[n][0] << endl;
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP