Cleaning Up (Usaco) - CTNCLN (vnoi)

Problem 2: Cleaning Up [Paul Christiano, 2007]

In the good old days, Farmer John served a boring cuisine comprising
but a single type of cow food to his N (1 <= N <= 40000) prize dairy
cows. Times change. Today he serves the herd a total of M (1 <= M
<= N) different types of food (conveniently numbered 1..M).

The cows are picky. Cow i has a single food preference P_i (1 <=
P_i <= M) and will eat only that favorite food.

Each day at feeding time FJ converts the barn into a tastefully lit
cafeteria. The cows line up outside to enter the cafeteria in order
of their previously-mentioned convenient index number.

Unfortunately, with so many types of food, cleaning up afterwards
is very time-consuming. If Farmer John is serving K different types
of food, it takes him K*K units of time to clean the barn.

To save time, FJ serves the cows in contiguous groups from the line.
After each group, he cleans up the barn and sets out the food for
the next group (of course, he only sets out food that cows in the
any given group will eat). Determine the minimum amount of total
time FJ must spend cleaning the barn. Each group consists of the
next contiguous group of cows from the line; each cow belongs to
exactly one group; and the barn must be cleaned up after every
group, including the last one.

PROBLEM NAME: cleanup

INPUT FORMAT:

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 contains a single integer: P_i

SAMPLE INPUT (file cleanup.in):

13 4
1
2
1
3
2
2
3
4
3
4
3
1
4

INPUT DETAILS:

There are four types of food and thirteen cows in line. The first
cow prefers type 1, the second type 2, the third type 1, etc.

OUTPUT FORMAT:

* Line 1: A single integer: the minimum amount of time FJ must spend
        cleaning the  barn.

SAMPLE OUTPUT (file cleanup.out):

11

OUTPUT DETAILS:

The first four groups contain one cow each. The fifth group contains
two cows who prefer food #2 (requiring one unit of time). The sixth
group contains cows preferring foods 3, 4, 3, 4, 3 (and requires
four units of time to clean). The last two groups contain one cow
each. The total time is 11.

vnoi:

Cho N số nguyên dương A1,A2...An. Mỗi số có giá trị không vượt quá N .

Yêu cầu :

Hãy chia N số này thành một số nhóm sao cho:

-Mỗi nhóm là một dãy các số liên tiếp.

-Trọng số của mỗi nhóm được tính theo công thức : Bình phương của số giá trị khác nhau trong nhóm đó.

        VD + 1 2 3 -> số giá trị khác nhau bằng 3 .

             + 1 2 1  -> số giá trị khác nhau bằng 2.

             + 1 1 1  -> số giá trị khác nhau bằng 1.

+Trọng số của dãy số bằng Tổng trọng số của tất cả các nhóm . Hãy tìm cách chia sao cho Tổng trọng số đạt giátrị nhỏ nhất.

Input

Dòng 1 : Gồm 2 số N và M - Số lượng số và số giá trị khác nhau trong dãy.

Dòng 2..N+1 : Mỗi dòng chứa một ố nguyên .

Output

Trọng số nhỏ nhất của dãy số.

Example

Input:

13 4
1
2
1
3
2
2
3
4
3
4
3
1
4
Output:
 11

Giải thích : Chúng ta sẽ chia dãy ố thành 8 nhóm 
+ 4 nhóm đầu tiên mỗi nhóm chứa một số duy nhất.
+ nhóm thứ 5 chứa hai số nguyên đều có giá trị là 2.
+ nhóm thứ 6 gồm các số từ 7->12 : (3, 4, 3, 4, 3)
+ 2 nhóm cuối cùng mỗi nhóm gồm 1 số duy nhất.

Kết quả là 1^2 + 1^2 + 1^2  + 1^2 + 1^2 + 2^2 + 1^2  + 1^2= 11.

Giới hạn: N<=40000.




Analysis:

USACO MAR09 Problem 'cleanup' Analysis

by Jaehyun Park

This is a one-dimensional DP problem. Let D[i] be the minimum amount of time needed to serve cows from 1 to i. Then D[i] is equal to the minimum value of D[k]+t(k+1, i)², for every k such that 0 <= k < i, where t(s, e) denotes the number of different types of food in the interval from s through e, inclusive. The time complexity of the algorithm is O(N²), which is too slow for the given problem.
The most important observation is that the number of different types of food within a single interval can be at most sqrt(N). If the number of different types exceeds sqrt(N), the minimum amount of time needed is at least N, but we can always get a solution of N unit times by diving the whole into groups of one.
Another minor point is that if two intervals with same end point have the same number of different types, it is always advantageous to use the longer interval, since D[i] increases as i increases.
These two observations enable us to consider only sqrt(N) different maximal intervals to calculate the value of D[i] for each i. To do so, we maintain another array of size sqrt(N) to store the minimum indices that is reachable from i with a given number of different types of food. By using the previous information, it is possible to update this array in O(sqrt(N)) time. Then the time complexity of the program is O(N^1.5), which is a huge improvement. For more detail, refer to the sample solution below.
The Korean version of the analysis is here.

//cleanup by Jaehyun Park

#include <stdio.h>
#define PROBNAME "cleanup"
#define min(a, b) (((a)<(b))?(a):(b))
#define sqr(x) ((x)*(x))
int N, M;
int P[40001];
int last_occurrence[40001];
int min_index[201], min_index_size;
int d[40001];
FILE *ifp=fopen(PROBNAME".in", "r");
FILE *ofp=fopen(PROBNAME".out", "w");

void INPUT() {
    int i;
    fscanf (ifp, "%d%d", &N, &M);
    for (i = 1; i <= N; i++)
        fscanf (ifp, "%d", &P[i]);
    P[0] = -1;
}

void PROCESS() {
    int i, j, k;
    for (i = 1; i <= M; i++)
        last_occurrence[i] = -1;
    for (min_index_size=1; sqr(min_index_size) <= N; min_index_size++);
    min_index_size--;
    min_index[0]=1;
    for(i=1;i<=N;i++) {
        k = last_occurrence[P[i]];
        for (j = 0; j <= min_index_size && min_index[j]-1 != k; j++)
            ;
        for(j--; j >= 0; j--)
            min_index[j+1]=min_index[j];
        min_index[0] = i + 1;
        d[i] = i;
        for (j = 1; j <= min_index_size; j++)
            d[i] = min(d[i], d[min_index[j]-1] + sqr (j));
        last_occurrence[P[i]] = i;
    }
}

void OUTPUT() {
    fprintf (ofp, "%d\n", d[N]);
}

void CLOSE_FILES() {
    fclose(ifp);
    fclose(ofp);
}

int main() {
    INPUT ();
    PROCESS ();
    OUTPUT ();
    CLOSE_FILES ();
    return 0;
}

http://ace.delos.com/MAR09.htm