Codeforces 319C (斜率优化DP)

本文主要是介绍Codeforces 319C (斜率优化DP)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

https://codeforces.com/contest/319/problem/C
思路： 问题转化为以最小的代价砍完第n棵树
f[i] 表示把i树砍完的最小代价， f[i] = min( f[j] + b[j] * a[i] )| 1<= j <= i - 1

f[j] = -ai * bi + fi
注意k 和 x 要是递增的, 这个题x是递减的，k也是递减的。我们让图像水平反转一下，就和普通斜率优化一样。
注意会爆ll

#include<bits/stdc++.h>
//#include <bits/extc++.h>
using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;
#define IOS ios::sync_with_stdio(false) ,cin.tie(0), cout.tie(0);  
//#pragma GCC optimize(3,"Ofast","inline")
#define ll long long
#define ull unsigned long long
#define li __int128_t
#define PII pair<int, int>
#define re register
//#define int long long
const int N = 2e5 + 5;
const int M = 1e6 + 5;
const int mod = 1e9 + 7;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
ll a[N], b[N], dp[N]; int q[N];
ll Y( int i ) { return dp[i]; }
ll X( int i ) { return b[i]; }
ll get_dp ( int i, int j ) { return dp[j] + b[j] * a[i]; }
int main() {
  IOS
  int n; cin >> n;
  for ( int i = 1; i <= n; ++ i ) cin >> a[i];
  for ( int i = 1; i <= n; ++ i ) cin >> b[i];
  int hh = 0, tt = -1;
  q[++ tt] = 1;
  for ( int i = 2; i <= n; ++ i ) {
    while( hh < tt && Y(q[hh + 1]) - Y(q[hh]) <= (X(q[hh]) - X(q[hh + 1])) * a[i] ) ++ hh;
    dp[i] = get_dp(i, q[hh]);             //会爆ll
    while( hh < tt  && (Y(i) - 1.0 * Y (q[tt])) * (X(q[tt - 1]) - X(q[tt])) <= 1.0 * (Y(q[tt]) - Y (q[tt - 1])) * (X(q[tt]) - X(i)) ) -- tt;
    q[++ tt] = i;
  }
  cout << dp[n] << endl;
  return 0;
}

这篇关于Codeforces 319C (斜率优化DP)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！