2011-08-29 10:31:55Morris
a194. 死亡 FLAG
a194. 死亡 FLAG
作法 1 : 轉成 DAG 做一次 最少路徑覆蓋
/**********************************************************************************/
/* Problem: a194 "死亡 FLAG" from LIS | DAG | DFS */
/* Language: C */
/* Result: AC (940ms, 1216KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-27 22:30:49 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
int map[502][502], Mt[502];
char used[502];
int mx[502], my[502];
int DFS(int now) {
int a, i;
for(a = 0; a < Mt[now]; a++) {
i = map[now][a];
if(!used[i]) {
used[i] = 1;
if(my[i] == 0 || DFS(my[i])) {
mx[now] = i, my[i] = now;
return 1;
}
}
}
return 0;
}
main() {
int n, a, b, A[501];
while(scanf("%d", &n) == 1) {
memset(Mt, 0, sizeof(Mt));
for(a = 1; a <= n; a++)
scanf("%d", &A[a]);
for(a = 1; a <= n; a++)
for(b = a+1; b <= n; b++)
if(A[b] > A[a])
map[a][Mt[a]++] = b;
memset(mx, 0, sizeof(mx));
memset(my, 0, sizeof(my));
int Ans = 0;
for(a = 1; a <= n; a++)
if(!mx[a]) {
memset(used, 0, sizeof(used));
if(DFS(a))
Ans++;
}
printf("%d\n", n-Ans);
}
return 0;
}
作法 2 : 反向求一個非嚴格遞增的 LIS, 或者是正向的一個非嚴格遞減的 LDS
/**********************************************************************************/
/* Problem: a194 "死亡 FLAG" from LIS | DAG | DFS */
/* Language: C */
/* Result: AC (54ms, 216KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-28 14:56:39 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
int A[502], pos[502], LIS[502];
int Search(int l, int r, int v) {
int m, L = r;
if(l > r) return 0;
do {
m = (l+r)/2;
if(LIS[m] <= v) {
if(m == L || LIS[m+1] > v)
return m+1;
l = m+1;
} else
r = m-1;
}while(l <= r);
return 0;
}
int DP_LIS(int n) {
int i, L = -1, set;
for(i = 0; i < n; i++) {
set = Search(0, L, A[i]);
LIS[set] = A[i], pos[i] = set;
if(set >= L) L = set;
}
return L+1;
}
main() {
int i, n;
while(scanf("%d", &n) == 1) {
for(i = n-1; i >= 0; i--)
scanf("%d", &A[i]);
printf("%d\n", DP_LIS(n));
}
return 0;
}
內容 ：
最近小光解題總是不順利, 難題寫不出來也就算了, 連簡單題都得到一堆 WA
後來他發現當自己興致一來的時候, 寫得題目可以越來越難, 但是一寫到比之前還簡單的題目, 他就會立刻立起 死亡 FLAG
這個時候只好先放下手頭上的題目, 休息一下再重新開始
但是小光對於解題總是有恐懼感, 他能很明確地排出哪道題目寫完, 後面的題目才解得出來, 接下來就交給你了
為了讓小光解題更加地順暢, 請你排完小光解題順序後, 輸出最少的休息次數
※ 小光一開始上場前, 就有休息過了
在一旁解題的 example 就直接來吐槽了下, 你的解題方式簡直跟 LIS 一模一樣嘛,
只不過需要用最少不重疊的 LIS 覆蓋所有數列上的所有點罷了
輸入說明
：
有多筆測資, 每筆第一行, 有一個數字 N, 代表接下來有 N 個題目等待解題, (1 ≦ N ≦ 500)
下一行, 有 N 個數字 P, 代表題目難度(1 ≦ P ≦ 2147483647)
輸出說明
：
輸出當小光解完所有的題目時, 小光最少的休息次數
範例輸入 ：
5 1 2 3 4 5 5 5 4 3 2 1 7 1 3 5 8 2 6 7
範例輸出 ：
1 5 2
提示
：
※ 待請 example 編輯題目內容
第一筆測資: 休息 1 → 2 → 3 → 4 → 5
第二筆測資: 休息 5 休息 4 休息 3 休息 2 休息 1
第三筆測資: 休息 1 → 2 → 6 → 7 休息 3 → 5 → 8
出處
：
LIS | DAG | DFS
(管理：morris1028)
作法 1 : 轉成 DAG 做一次 最少路徑覆蓋
/**********************************************************************************/
/* Problem: a194 "死亡 FLAG" from LIS | DAG | DFS */
/* Language: C */
/* Result: AC (940ms, 1216KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-27 22:30:49 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
int map[502][502], Mt[502];
char used[502];
int mx[502], my[502];
int DFS(int now) {
int a, i;
for(a = 0; a < Mt[now]; a++) {
i = map[now][a];
if(!used[i]) {
used[i] = 1;
if(my[i] == 0 || DFS(my[i])) {
mx[now] = i, my[i] = now;
return 1;
}
}
}
return 0;
}
main() {
int n, a, b, A[501];
while(scanf("%d", &n) == 1) {
memset(Mt, 0, sizeof(Mt));
for(a = 1; a <= n; a++)
scanf("%d", &A[a]);
for(a = 1; a <= n; a++)
for(b = a+1; b <= n; b++)
if(A[b] > A[a])
map[a][Mt[a]++] = b;
memset(mx, 0, sizeof(mx));
memset(my, 0, sizeof(my));
int Ans = 0;
for(a = 1; a <= n; a++)
if(!mx[a]) {
memset(used, 0, sizeof(used));
if(DFS(a))
Ans++;
}
printf("%d\n", n-Ans);
}
return 0;
}
作法 2 : 反向求一個非嚴格遞增的 LIS, 或者是正向的一個非嚴格遞減的 LDS
/**********************************************************************************/
/* Problem: a194 "死亡 FLAG" from LIS | DAG | DFS */
/* Language: C */
/* Result: AC (54ms, 216KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-28 14:56:39 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
int A[502], pos[502], LIS[502];
int Search(int l, int r, int v) {
int m, L = r;
if(l > r) return 0;
do {
m = (l+r)/2;
if(LIS[m] <= v) {
if(m == L || LIS[m+1] > v)
return m+1;
l = m+1;
} else
r = m-1;
}while(l <= r);
return 0;
}
int DP_LIS(int n) {
int i, L = -1, set;
for(i = 0; i < n; i++) {
set = Search(0, L, A[i]);
LIS[set] = A[i], pos[i] = set;
if(set >= L) L = set;
}
return L+1;
}
main() {
int i, n;
while(scanf("%d", &n) == 1) {
for(i = n-1; i >= 0; i--)
scanf("%d", &A[i]);
printf("%d\n", DP_LIS(n));
}
return 0;
}
上一篇：d739. 最少路径覆盖
下一篇：d449. 垃圾信件