NCPC2012C Matrix
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, bi,j is less than bi+1,j, where bi,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 kmax 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 kmax.
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 kmax in a new line.
範例輸入 ：
22 36 3 51 4 23 23 12 46 5
範例輸出 ：
23
提示 ：
出處 ：
很明顯地, 我們必須先將每個集合元素 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;
}