Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Problem B: Situp Benches

The gym at the University of Alberta has two identical sit up benches that are side by side. Each of these benches can be inclined in 10 degree increments between 10 degrees and 50 degrees inclusive depending on the level of difficulty the user desires. At the end of each day the gym staff adjust the incline of each machine to be 10 degrees. This means at the start of each day both machines have a 10 degree incline.

Every time someone uses a bench it incurs some wear and tear that amounts to 15 cents in maintenance costs. Additionally, every time a bench has its incline changed it incurs wear and tear that amounts to the number of degrees the bench was adjusted, in cents. For example, if someone moves the bench from a 40 degree incline to a 20 degree incline then 20 cents of maintenance must be done.

The gym staff have recently required students to sign up for the situp benches the day before. When a student signs up they give the time at which they would like to use the machine and the incline they will use it at. No more than two students can sign up to use a bench at the same time.

Prior to opening the gym for the day, the gym staff would like to have a list assigning students to each of the situp benches and they would like the assignment to minimize the total maintenance cost for the day. They have asked you to write a program to make this list.

Input begins with the number of test cases on its own line. Each test case begins with the number n (1 ≤ n ≤ 10000), the number of students who have signed up to use the benches on the following day. Following are n lines, each consisting of two numbers: time_slot and incline. time_slot is a number that specifies when a student will arrive at the machine, while incline specifies the angle to which they will adjust the situp bench. Two students in the same time_slot arrive at the benches at the same time, and lower time_slots occur before higher time_slots. time_slots are numbered between 0 and 20000, and incline is one of 10, 20, 30, 40 or 50 depending on the student's preference.

For each test case, output a line containing the total maintenance cost (in cents) for the day followed by n lines (one for each student, in the order given on input) containing either a 1 or a 2 depending on which bench you have assigned them to. Any assignment that minimizes the total maintenance cost for the day is acceptable.

Sample Input

1
3
2 40
2 50
1 40

Sample Output

185
1
2
1

---

dp[time][第一台位置][第二台位置]去做轉移

#include <stdio.h>
#include <stdlib.h>
#define min(x,y) ((x)<(y)?(x):(y))
typedef struct {
    int t, c, in;
} St;
int cmp(const void *i, const void *j) {
    return ((St *)i)->t - ((St *)j)->t;
}
int cmp_out(const void *i, const void *j) {
    return ((St *)i)->in - ((St *)j)->in;
}
int st[10005][6][6][5];
int main() {
    int t, n, i, j, k;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        St D[10005];
        for(i = 0; i < n; i++)
            scanf("%d %d", &D[i].t, &D[i].c), D[i].c /= 10, D[i].in = i;
        qsort(D, n, sizeof(St), cmp);
        int dp[10005][6][6] = {}, ch = 0;
        for(i = 1; i <= 5; i++)
            for(j = 1; j <= 5; j++)
                dp[0][i][j] = 0xfffffff;
        dp[0][1][1] = 0;
        for(i = 0; i < n; i++) {
            ch++;
            for(j = 1; j <= 5; j++)
                for(k = 1; k <= 5; k++)
                    dp[ch][j][k] = 0xfffffff;
            if(i+1 < n && D[i+1].t == D[i].t) {
                st[ch][D[i].c][D[i+1].c][0] = 2;/*[0]cnt*/
                st[ch][D[i+1].c][D[i].c][0] = 2;
                for(j = 1; j <= 5; j++) {
                    for(k = 1; k <= 5; k++) {
                        if(dp[ch][D[i].c][D[i+1].c] > dp[ch-1][j][k]+abs(j-D[i].c)+abs(k-D[i+1].c)) {
                            dp[ch][D[i].c][D[i+1].c] = dp[ch-1][j][k]+abs(j-D[i].c)+abs(k-D[i+1].c);
                            st[ch][D[i].c][D[i+1].c][1] = j;/*state*/
                            st[ch][D[i].c][D[i+1].c][2] = k;
                            st[ch][D[i].c][D[i+1].c][3] = 1;/*choose*/
                            st[ch][D[i].c][D[i+1].c][4] = 2;
                        }
                        if(dp[ch][D[i+1].c][D[i].c] > dp[ch-1][j][k]+abs(k-D[i].c)+abs(j-D[i+1].c)) {
                            dp[ch][D[i+1].c][D[i].c] = dp[ch-1][j][k]+abs(k-D[i].c)+abs(j-D[i+1].c);
                            st[ch][D[i+1].c][D[i].c][1] = j;
                            st[ch][D[i+1].c][D[i].c][2] = k;
                            st[ch][D[i+1].c][D[i].c][3] = 2;
                            st[ch][D[i+1].c][D[i].c][4] = 1;
                        }
                    }
                }
                i++;
            } else {
                for(j = 1; j <= 5; j++) {
                    for(k = 1; k <= 5; k++) {
                        if(dp[ch][D[i].c][k] > dp[ch-1][j][k]+abs(j-D[i].c)) {
                            dp[ch][D[i].c][k] = dp[ch-1][j][k]+abs(j-D[i].c);
                            st[ch][D[i].c][k][0] = 1;
                            st[ch][D[i].c][k][1] = j;
                            st[ch][D[i].c][k][2] = k;
                            st[ch][D[i].c][k][3] = 1;
                        }
                        if(dp[ch][j][D[i].c] > dp[ch-1][j][k]+abs(k-D[i].c)) {
                            dp[ch][j][D[i].c] = dp[ch-1][j][k]+abs(k-D[i].c);
                            st[ch][j][D[i].c][0] = 1;
                            st[ch][j][D[i].c][1] = j;
                            st[ch][j][D[i].c][2] = k;
                            st[ch][j][D[i].c][3] = 2;
                        }
                    }
                }
            }
        }
        int ans = 0xfffffff;
        for(i = 1; i <= 5; i++)
            for(j = 1; j <= 5; j++)
                ans = min(ans, dp[ch][i][j]+i+j-2);
        int ti, tj;
        for(i = 1; i <= 5; i++)
            for(j = 1; j <= 5; j++)
                if(ans == dp[ch][i][j]+i+j-2)
                    ti = i, tj = j;
        int pel = n-1;
        while(ch > 0) {
            if(st[ch][ti][tj][0] == 1) {
                D[pel].t = st[ch][ti][tj][3];
                int tti = st[ch][ti][tj][1];
                int ttj = st[ch][ti][tj][2];
                ti = tti, tj = ttj;
                pel--;
            } else {
                D[pel].t = st[ch][ti][tj][4];
                D[pel-1].t = st[ch][ti][tj][3];
                int tti = st[ch][ti][tj][1];
                int ttj = st[ch][ti][tj][2];
                ti = tti, tj = ttj;
                pel -= 2;
            }
            ch--;
        }
        qsort(D, n, sizeof(St), cmp_out);
        ans = ans*10 + n*15;
        printf("%d\n", ans);
        for(i = 0; i < n; i++)
            printf("%d\n", D[i].t);
    }
    return 0;
}