Massive Algorithms: E. Ciel and Gondolas

E. Ciel and Gondolas - Codeforces Round #190

https://blog.csdn.net/cqbzwja/article/details/50916994 https://codeforces.com/contest/321/problem/E

Fox Ciel is in the Amusement Park. And now she is in a queue in front of the Ferris wheel. There are n people (or foxes more precisely) in the queue: we use first people to refer one at the head of the queue, and n-th people to refer the last one in the queue.

There will be k gondolas, and the way we allocate gondolas looks like this:

When the first gondolas come, the q1 people in head of the queue go into the gondolas.
Then when the second gondolas come, the q2 people in head of the remain queue go into the gondolas.
...
The remain qk people go into the last (k-th) gondolas.

Note that q1, q2, ..., qk must be positive. You can get from the statement that $\text{[math]}$ and qi > 0.

You know, people don't want to stay with strangers in the gondolas, so your task is to find an optimal allocation way (that is find an optimal sequence q) to make people happy. For every pair of people i and j, there exists a value uij denotes a level of unfamiliar. You can assume uij = uji for all i, j (1 ≤ i, j ≤ n) and uii = 0 for all i (1 ≤ i ≤ n). Then an unfamiliar value of a gondolas is the sum of the levels of unfamiliar between any pair of people that is into the gondolas.

A total unfamiliar value is the sum of unfamiliar values for all gondolas. Help Fox Ciel to find the minimal possible total unfamiliar value for some optimal allocation.

Input

The first line contains two integers n and k (1 ≤ n ≤ 4000 and 1 ≤ k ≤ min(n, 800)) — the number of people in the queue and the number of gondolas. Each of the following n lines contains n integers — matrix u, (0 ≤ uij ≤ 9, uij = uji and uii = 0).

Please, use fast input methods (for example, please use BufferedReader instead of Scanner for Java).

Output

Print an integer — the minimal possible total unfamiliar value.

Examples

input
Copy
5 2
0 0 1 1 1
0 0 1 1 1
1 1 0 0 0
1 1 0 0 0
1 1 0 0 0

output
Copy
0

input
Copy
8 3
0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1
1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 0

output
Copy
7

input
Copy
3 2
0 2 0
2 0 3
0 3 0

output
Copy
2

Note

In the first example, we can allocate people like this: {1, 2} goes into a gondolas, {3, 4, 5} goes into another gondolas.

In the second example, an optimal solution is : {1, 2, 3} | {4, 5, 6} | {7, 8}

https://codeforces.com/blog/entry/8192

n(n≤4000)n(n≤4000)个人排队要乘k(k≤min(n,800))k(k≤min(n,800))艘船，每艘船坐的人数不限。第i个人对第j个人有一个不满意度Ui,j(0≤Ui,j≤9且Ui,j=Uj,i=0)Ui,j(0≤Ui,j≤9且Ui,j=Uj,i=0)，如果他们在一条船中的话。问，如何安排使得总不满度最小。
DP，满足四边形不等式。
f(i,j)f(i,j)表示前面j个人乘坐i只船的不满度，那么f(i,j)=min(f(i−1,k)+w(k+1,j)|i−1≤k<j)f(i,j)=min(f(i−1,k)+w(k+1,j)|i−1≤k<j)，其中w(k+1,j)w(k+1,j)是第k+1个人到第j个人在同一艘船中的不满度，通过O(n2)O(n2)的时间复杂度求出来。

https://blog.csdn.net/jaihk662/article/details/83030345

bzoj5311：https://www.lydsy.com/JudgeOnline/problem.php?id=5311

同一道题目，但是bzoj可能需要读入挂

决策单调性Ⅰ：四边形不等式

wqs二分

https://www.codetw.com/epfpxp.html

題意：N個人排成一行，分成K組，要求每組的不和諧值之和最小。

思路：開始以為是斜率優化DP，但是每個區間的值其實已經知道了，即是沒有和下標有關的未知數了，所以沒必要用斜率。四邊形優化。

dp[i][j]表示前j個人分為i組的最小代價。

然后发现每层当n向右移动的时候，决策点一定向右移动

（可能可以观察+证明）

然后用整体二分trick就可以了。复杂度

O (K n l o g n)

。

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;
}

X. https://www.cnblogs.com/galaxies/p/cf321E.html

首先有一个

O (n^{2} k)

的dp。

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;
}

X. https://blog.csdn.net/jaihk662/article/details/83030345
最无脑的暴力DP是O(n²k的)，dp[x][y]表示前x个贞鱼上了k辆车的怨气最小值，对于每个状态O(n)转移

→这个就不用多说了，入门DP，复杂度上天

有点经验的话可以看出（猜测）这个DP是有决策单调性的，这样的话就可以nlogn进行整体转移，复杂度O(nklogn)

很遗憾这样还是超时，因为k*n已经接近/超过亿级别，再加个logn肯定不行

想办法消掉k，这有个经典操作：wqs二分（https://www.cnblogs.com/CreeperLKF/p/9045491.html）

一般来讲用来应付一些这样的题目：给了一个选物品的限制条件，要求刚好选k个，让你最大化（最小化）权值（代价），然后其特点就是当选的物品越多的时候权值越大（越小）

一道非常经典的模板题如下：给你一个n个点m条边无向带权连通图，每条边是黑色或白色，让你求一棵最小权的恰好有k条白色边的生成树（bzoj2654）

正解就是二分权值val，让后让所有的白边权值全部加上val，跑一下Kruskal，然后看一下最小生成树中有多少条白色边

如果白色边个数>k，增加val的值继续二分
如果白色边个数<k，减少val的值继续二分
直到最小生成树中刚好有k条白边位置，直接减去val*k就是答案

这道题当然如出一辙：二分val，每多选一辆车就加上额外val点代价，看最后DP完之后选了多少辆车，如果不到k辆就减少val，否则增大val，搞定，时间复杂读O(nlognlogW)，其中W为val最大可能

https://blog.csdn.net/Izumi_Hanako/article/details/80275299

E. Ciel and Gondolas - Codeforces Round #190

Labels

Popular Posts