首页 > 代码库 > Codeforces 321E Ciel and Gondolas
Codeforces 321E Ciel and Gondolas
传送门:http://codeforces.com/problemset/problem/321/E
【题解】
首先有一个$O(n^2k)$的dp。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10, N = 4000 + 5; const int mod = 1e9+7; const ll inf = 1e17; inline int getint() { int x = 0; char ch = getchar(); while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) x = (x<<3) + (x<<1) + ch - ‘0‘, ch = getchar(); return x; } int n, K, a[N][N], d[N][N]; ll f[805][N]; int main() { n = getint(), K = getint(); for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + getint(); for (int i=1; i<=n; ++i) { d[i][i] = 0; for (int j=i+1; j<=n; ++j) d[i][j] = (a[j][j] - a[j][i-1] - a[i-1][j] + a[i-1][i-1])/2; } for (int i=1; i<=n; ++i) f[0][i] = inf; for (int i=1; i<=K; ++i) { for (int j=1; j<=n; ++j) { f[i][j] = inf; for (int k=0; k<j; ++k) f[i][j] = min(f[i][j], f[i-1][k] + d[k+1][j]); } } cout << f[K][n]; return 0; }
然后发现每层当n向右移动的时候,决策点一定向右移动
(可能可以观察+证明)
然后用整体二分trick就可以了。复杂度$O(Knlogn)$。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10, N = 4000 + 5; const int mod = 1e9+7; const ll inf = 1e17; inline int getint() { int x = 0; char ch = getchar(); while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) x = (x<<3) + (x<<1) + ch - ‘0‘, ch = getchar(); return x; } int n, K, a[N][N], d[N][N]; ll f[805][N], *F, *G; inline void solve(int l, int r, int al, int ar) { if(l > r) return ; int mid = l+r>>1; ll mx = inf, t; int pos = 0; for (int j=al; j<=ar && j<mid; ++j) if((t = G[j] + d[j+1][mid]) < mx) mx = t, pos = j; F[mid] = mx; solve(l, mid-1, al, pos); solve(mid+1, r, pos, ar); } int main() { n = getint(), K = getint(); for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + getint(); for (int i=1; i<=n; ++i) { d[i][i] = 0; for (int j=i+1; j<=n; ++j) d[i][j] = (a[j][j] - a[j][i-1] - a[i-1][j] + a[i-1][i-1])/2; } for (int i=1; i<=n; ++i) f[0][i] = inf; for (int i=1; i<=K; ++i) { F = f[i], G = f[i-1]; solve(1, n, 0, n); } cout << f[K][n]; return 0; }
Codeforces 321E Ciel and Gondolas
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。