挑战程序设计竞赛-day2

Crazy Rows

给定一个由0和1组成的矩阵。只允许交换相邻的两行（第$i$行和第$i+1$行），要把矩阵化成下三角矩阵（主对角线上方的元素都是0），最少需要交换几次？输入的矩阵保证总能化成下三角矩阵。

输入

N = 3
001
100
010

输出

2（交换第1行和第2行，再交换第2行和第3行，得到下三角矩阵）

思路：

暂且先考虑一下最后应该把哪一行交换到第一行。最后的第一行应该具有00…0或是10…0的形式。可以交换到第1行的行当然也可以换到第2行及之后的行，当有多个满足条件的行时，选择距离第1行近的行对应的最终费用要小。对于之后的行就可以以同样的思路处理。

在这道题中，每行的0和1的位置并不重要，只要知道每行最后一个1所在的位置就足够了。如果先将这些位置预先计算好，那么就能降低行交换时的复杂度。直接按矩阵的形式处理的复杂度是$O(N^3)$，而预先计算后再处理的复杂度降为$O(N^2)$

// 输入
int N;
int M[MAX_N][MAX_N];    // 矩阵

int a[MAX_N];       // a[i]表示第i行最后出现1的位置 1~n-1

void solve() {
    int res = 0;
    for(int i = 0; i < N; i++) {
        int pos = -1;  //  如果第i行不含1的话，就当做-1
        for(int j = i; j < N; j++) {
            if(a[j] <= i) {
                pos = j;
                break;
            }
        }

        // 完成交换
        for(int j = pos; j > i; j++) {
            swap(a[j], a[j - 1]);
            res++;
        }
    }
    printf("%d\n", res);
}

Bribe the Prisoners

输入

P = 20,	 Q = 3, A = {3, 6, 14}

输出

35（按照14，6，3的熟悉怒释放，则需要19+12+4=35枚金币，是最少的）

思路：动态规划

const int MAX_Q = 20;
int P, Q, A[MAX_Q + 2];

// dp[i][j]表示的是，将从A[i]号囚犯到A[j]号囚犯(不含两端的囚犯)的连续部分里的所有囚犯都释放时，所需的最少金币总数。
int dp[MAX_Q + 1][MAX_Q + 2];

void solve() {
    // 为了处理方便，将两端加入A中
    A[0] = 0;
    A[Q + 1] = P + 1;
    // 初始化
    for(int q = 0; q <= Q; q++) {
        dp[q][q + 1] = 0;
    }

    // 从短的区间开始填充dp
    for(int w = 2; w <= Q + 1; w++) {
        for(int i = 0; i + w <= Q + 1; i++) {
            // 计算dp[i][j]
            int j = i + w, t = INT_MAX;
            // 枚举最初释放的囚犯，计算最小的费用
            for(int k = i + 1; k < j; k++) {
                t = min(t, dp[i][k] + dp[k][j]);
            }

            // 最初的释放还需要与所释放囚犯无关的A[j] - A[i] - 2枚金币
            dp[i][j] = t + A[j] - A[i] - 2;
        }
    }
    printf("%d\n", dp[0][Q + 1]);
}