2015
02-22

# Anti LIS

Haven’t you heard about Lost?
Having written a article named <Summaries of ALL Algorithms>, Lost is good at solved by algorithm problems(?). One day, GXX asked Lost to work out the Longest Increasing Subsequence(for short, LIS) of a given sequence {A_1, A_2, …, A_N}. Knowing this problem well, Lost simply copied a program from his article and solved the problem in seconds. So that GXX became frustrated. She wanted to cheat Lost by removing some elements from the original sequence to make Lost’s answer go wrong. For convinience, she would like to remove least number of elements.

The beginning of the input is an integer T(T <= 10), which is the number of test cases. T cases are followed. The first line of each test case is an integer N (1 <= N <= 1,000), which denotes the length of the sequence. The second line is N integer A_1, A_2, …, A_N, which denote the given sequence.

The beginning of the input is an integer T(T <= 10), which is the number of test cases. T cases are followed. The first line of each test case is an integer N (1 <= N <= 1,000), which denotes the length of the sequence. The second line is N integer A_1, A_2, …, A_N, which denote the given sequence.

1
6
10 10 20 1 2 2

2

#include <stdio.h>
#include <string.h>
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define INF 0x7fffffff
#define MAXN 2010
#define MAXM 600000

int pt[MAXM], head[MAXN], next[MAXM], flow[MAXM], lvl[MAXN], queue[MAXN];
int pos;

int arr[MAXN], stage[MAXN];
int n;

void AddEdge(int a, int b, int c)
{
pt[++pos] = b;
next[pos] = head[a];
head[a] = pos;
flow[pos] = c;
}

void Connect(int a, int b, int c)
{
AddEdge(a, b, c);
AddEdge(b, a, 0);
}

bool bfs(int s, int t)
{
int qs, qe, v, e;
memset (lvl, 0, sizeof lvl);
lvl[s] = 1;
qs = qe = 0;
queue[qe++] = s;
while (qs < qe)
{
v = queue[qs++];
//printf("v = %d\n", v);
for (e = head[v]; e != -1; e = next[e])
if (flow[e] > 0 && lvl[pt[e]] == 0)
{
lvl[pt[e]] = lvl[v] + 1;
queue[qe++] = pt[e];
}
}
return lvl[t] > 0;
}

int Update(int v, int t, int tmpflow)
{
//printf("v = %d flow = %d\n", v, tmpflow);
int tmp, res = 0, e;
if (v == t) return tmpflow;
for (e = head[v]; e != -1; e = next[e])
if (flow[e] > 0 && lvl[pt[e]] == lvl[v] + 1)
{
tmp = Update(pt[e], t, MIN(flow[e], tmpflow));
flow[e] -= tmp; flow[e^1] += tmp;
res += tmp;
tmpflow -= tmp;
if (tmpflow == 0) {break;}
}
lvl[v] = -1;
return res;
}

int dinic(int s, int t)
{
int res = 0;
while (bfs(s, t))
res += Update(s, t, INF);
return res;
}

void GenStage(int n)
{
int i, j, mx = -1;
memset (stage, 0, sizeof stage);
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
if (arr[j] > arr[i])
stage[j] = MAX(stage[j], stage[i] + 1);
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
if (stage[i] + 1 == stage[j] && arr[i] < arr[j])
Connect(2 * i + 1, 2 * j, INF);
for (i = 0; i < n; i++)
{
// printf("%d ", stage[i]);
mx = MAX(mx, stage[i]);
}
// printf("\n");
for (i = 0; i < n; i++)
{
Connect(2 * i, 2 * i + 1, 1);
if (stage[i] == 0)
Connect(2 * n, 2 * i, INF);
if (stage[i] == mx)
Connect(2 * i + 1, 2 * n + 1, INF);
}
}

void Solve()
{
int i, res;
memset (head, -1, sizeof head);
pos = -1;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", arr + i);
GenStage(n);
res = dinic(2 * n, 2 * n + 1);
printf("%d\n", res);
}

int main()
{
int cas;
scanf("%d", &cas);
while (cas--)
Solve();
return 0;
}


1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

2. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环

3. 第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。