Yet Another Minimization Problem

dp方程我們很容易能得出， f[ i ] = min(g[ j ] + w( j + 1, i ))。 然后感覺就根本不能優化。

然后就滾去學決策單調啦。 然后就是個裸題， 分治一下就好啦，

注意用分治找決策點需要的條件是我們找出被決策點不能作為當前轉移的決策點使用。

如果w( j + 1, i )能很方便求出就能用單調棧維護， 并且找出的被決策點能當作當前轉移的決策點使用。

我怎么感覺用bfs應該跑莫隊的時候應該比dfs快啊， 但是居然還是dfs跑得快， 莫名其妙。。

#include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define PLL pair<LL, LL> #define PLI pair<LL, int> #define PII pair<int, int> #define SZ(x) ((int)x.size()) #define ull unsigned long longusing namespace std;const int N = 1e5 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9 + 7; const double eps = 1e-8; const double PI = acos(-1);int n, k, a[N], cnt[N]; LL f[N], g[N];int pl = 1, pr = 0; LL val;inline LL w(int i, int j) {while(pl > i) pl--, val += cnt[a[pl]], cnt[a[pl]]++;while(pr < j) pr++, val += cnt[a[pr]], cnt[a[pr]]++;while(pl < i) cnt[a[pl]]--, val -= cnt[a[pl]], pl++;while(pr > j) cnt[a[pr]]--, val -= cnt[a[pr]], pr--;return val; }void solve(int L, int R, int l, int r) {if(l > r) return;int mid = l + r >> 1, p = L;for(int i = L; i <= min(R, mid); i++)if(g[i] + w(i + 1, mid) < f[mid])f[mid] = g[i] + w(i + 1, mid), p = i;solve(L, p, l, mid - 1);solve(p, R, mid + 1, r); }int main() {scanf("%d%d", &n, &k);for(int i = 1; i <= n; i++) {scanf("%d", &a[i]);f[i] = f[i - 1] + cnt[a[i]];cnt[a[i]]++;}for(int i = 2; i <= k; i++) {memset(cnt, 0, sizeof(cnt));memcpy(g, f, sizeof(g));memset(f, INF, sizeof(f));solve(1, n, 1, n);}printf("%lld\n", f[n]);return 0; }/* */

?

轉載于:https://www.cnblogs.com/CJLHY/p/10507436.html

總結

以上是生活随笔為你收集整理的Codeforces 868F Yet Another Minimization Problem 决策单调性 (看题解)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。