NCPC2012C Matrix＠Morris' Blog｜PChome Online 個人新聞台

2012-10-22 07:18:53| 人氣626| 回應0 | 上一篇 | 下一篇

NCPC2012C Matrix

推薦 0 收藏 0 轉貼0 訂閱站台

Problem C

Matrix

Input File: pc.in

Time limit: 5 seconds

Given k sets, where k >= 2 and each set has n integers, they are said to be compatible if a k×n matrix B can be constructed from them to meet the following two conditions:

l Each row of B is constructed from a different set and is a permutation of the integers in the corresponding set.

l For all i and j, 1 <= i <= k-1, 1 <= j <= n, b_i,j is less than b_i+1,j, where b_i,j is the element at the ith row and jth column of B.

For example, consider two sets {6,3,5} and {1,4,2}. The two sets are compatible because a 2×3 matrix B can be constructed as follows to meet the above two conditions. The first row of B is from the second set and is [1 4 2], while the second row of B is from the first set and is [3 6 5].

Now consider m (m >= 2) sets each of which has n integers. Also assume that among the m sets, at least two of them are compatible. There are many possible ways to select k (2 <= k <= m) sets from the m sets. Let k_max denote the largest number of sets which are selected from the m sets and are compatible. Your task is to write a program that computes k_max.

Technical Specification

l The number of sets, m, is at least 2 and at most 2500. At least two of the m sets are compatible. The number of integers in each of the m sets, n, is at least 1 and at most 20. Each integer in a set is at least 1 and at most 50000.

輸入說明：

The first line of the input file contains an integer, denoting the number of test cases to follow. For each test case, the first line contains two positive integers m and n, respectively denoting the number of sets and the number of integers in each set; in the next m lines, each line gives n integers for a set.

輸出說明：

For each test case, output its k_max in a new line.

範例輸入： help

22 36 3 51 4 23 23 12 46 5

範例輸出：

提示：

出處：

NCPC2012 (管理：morris1028)

根據題目意思, 是要從很多集合中, 挑出一序列的集合當作 B 矩陣的 row, 且兩兩相鄰的 row 要符合給定的全小於另一row的規定, 求最多的 row。

很明顯地, 我們必須先將每個集合元素 sort 過, 然後再將這些元素集合按照字典順序排序過, 然後接著找出 LIS 長度。

#include <cstdio>
#include <algorithm>
using namespace std;
int M[2505][35], IM[2505];
int n, m;
bool cmp(int a, int b) {
    static int i;
    for(i = 0; i < m; i++)
        if(M[a][i] != M[b][i])
            return M[a][i] < M[b][i];
    return true;
}
bool cmp2(int a, int b) {
    static int i;
    for(i = 0; i < m; i++)
        if(M[a][i] >= M[b][i])
            return false;
    return true;
}
int main() {
    int t, i, j;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &m);
        for(i = 0; i < n; i++) {
            for(j = 0; j < m; j++)
                scanf("%d", &M[i][j]);
            sort(M[i], M[i]+m);
            IM[i] = i;
        }
        sort(IM, IM+n, cmp);
        int dp[2505] = {}, ans = 0;
        for(i = 0; i < n; i++) {
            for(j = 0; j < i; j++) {
                if(cmp2(IM[j], IM[i])) {
                    dp[i] = max(dp[i], dp[j]+1);
                }
            }
            ans = max(dp[i], ans);
        }
        printf("%d\n", ans+1);
    }
    return 0;
}

我要檢舉

#NCPC

台長： Morris

您可能對以下文章有興趣

a250. NCPC2011 Problem H Special Subsequences

[ZJ][N*NlogN][BIT] a533. IOI2004 Day1.1.阿特米斯

[ZJ][DP] a365. 3. 新井字遊戲

d598. 3. 尋寶問題 (粗糙濫造版本)

人氣(626) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[ZJ][dp] b220. 5. 蛋糕師傅的煩惱
此分類上一篇:NCPC2012F Optimal Transformation Cost

回應(0)