P4072 [SDOI2016]征途
#include<bits/stdc++.h>
using namespace std;
using cint = const int&;
using ll = long long;
constexpr ll maxn = 3e3 + 10, inf = 0x3f3f3f3f;
int sum[maxn], Q[maxn], n, m;
int dp[maxn][maxn];
#define x(k) sum[k]
inline const int y(cint p, cint k) { return (dp[p - 1][k] + sum[k] * sum[k]); }
#define sp(i) 2*sum[i]
#define cval(i) sum[i]*sum[i]
template<typename T>
struct qqueue {
    unsigned top, back;
    T* q;
    inline T& operator[](const auto& p) { return p >= 0 ? q[top + p] : q[back + 1 + p]; }
    inline size_t size() { return back - top + 1; }
    inline bool empty() { return top > back; }
    inline void tie(T* const _date) { top = back = 1; q = _date; }
    inline void clear() { top = back = 1; }
    inline void poptop() { ++top; }
    inline void popback() { --back; }
    inline void pushback(const T& val) { q[++back] = val; }
    inline void pushtop(const T& val) { q[--top] = val; }
};
qqueue<int> q;
#define slope(p,a, b) y(p,a) - y(p,b),x(a) - x(b)
using slp = const pair<const int&, const int&>&;
inline bool spless(slp a, slp b) {return ((a.first * b.second) < (b.first * a.second)) ^ (a.second > 0) ^ (b.second > 0);}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    q.tie(Q);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)cin >> sum[i], sum[i] += sum[i - 1];
    for (int i = 1; i <= n; ++i) dp[1][i] = sum[i] * sum[i];
    for (int p = 2; p <= m; ++p) {
        q.clear();
        for (int i = p - 1; i <= n; ++i) {
            while ((q.size() > 1) && spless({ slope(p,q[0],q[1]) }, { sp(i),1 }))q.poptop();
            const auto top = q[0];
            //dp[p][i] = y(p, top) + sum[i] * sum[i] - sp(i) * x(top);
            dp[p][i] = dp[p - 1][top] + (sum[i] - sum[top]) * (sum[i] - sum[top]);
            while ((q.size() > 1) && spless({ slope(p, q[~0], i) }, { slope(p, q[~1], q[~0]) }))q.popback();
            q.pushback(i);
        }
    }
    cout << m * dp[m][n] - sum[n] * sum[n];
}

Tip

注意!!!!!重载函数有明显性能下降!

dp, 考虑转换 dp_i = \min{f(j)+g(i)s(j)}+t_i 为 斜率式,f(j)=y,g(i)=k,s(j)=x,dp_i-t_i=b

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇