1010. 拦截导弹
对偶问题:
对于一个序列,求:
最长上升子序列
最少用多少个费上升子序列可以覆盖整个序列
答案是一样的。
Dilworth 定理
Dilworth Wikipedia
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include <iostream> using namespace std;const int N = 1010 ;int f[N], g[N], a[N];int n;int main () { while (cin >> a[n]) n++; int res = 0 ; for (int i = 0 ; i < n; i++) { f[i] = 1 ; for (int j = 0 ; j < i; j++) { if (a[j] >= a[i]) { f[i] = max (f[i], f[j] + 1 ); } } res = max (res, f[i]); } cout << res << endl; int cnt = 0 ; for (int i = 0 ; i < n; i++) { int k = 0 ; while (k < cnt && g[k] < a[i]) k++; g[k] = a[i]; if (k >= cnt) cnt++; } cout << cnt << endl; return 0 ; }
187. 导弹防御系统
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include <iostream> using namespace std;const int N = 55 ;int up[N], down[N], a[N];int n;int ans;void dfs (int u, int su, int sd) { if (su + sd >= ans) return ; if (u == n) { ans = su + sd; return ; } int k = 0 ; while (k < su && up[k] >= a[u]) k++; int t = up[k]; up[k] = a[u]; if (k < su) dfs (u + 1 , su, sd); else dfs (u + 1 , su + 1 , sd); up[k] = t; k = 0 ; while (k < sd && down[k] <= a[u]) k++; t = down[k]; down[k] = a[u]; if (k < sd) dfs (u + 1 , su, sd); else dfs (u + 1 , su, sd + 1 ); down[k] = t; } int main () { while (cin >> n, n) { for (int i = 0 ; i < n; i++) cin >> a[i]; ans = n; dfs (0 , 0 , 0 ); cout << ans << endl; } return 0 ; }
272. 最长公共上升子序列
朴素解法,O ( n 3 ) O(n^3) O ( n 3 ) .
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include <iostream> using namespace std;const int N = 3010 ;int n;int f[N][N], a[N], b[N];int main () { scanf ("%d" , &n); for (int i = 1 ; i <= n; i++) scanf ("%d" , &a[i]); for (int i = 1 ; i <= n; i++) scanf ("%d" , &b[i]); for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= n; j++) { f[i][j] = f[i - 1 ][j]; if (a[i] == b[j]) { f[i][j] = max (f[i][j], 1 ); for (int k = 1 ; k < j; k++) { if (b[k] < b[j]) { f[i][j] = max (f[i][j], f[i][k] + 1 ); } } } } } int res = 0 ; for (int i = 1 ; i <= n; i++) res = max (res, f[n][i]); printf ("%d\n" , res); return 0 ; }
优化掉最内部的循环,达到 O ( n 2 ) O(n^2) O ( n 2 ) .
1 2 3 4 5 6 7 8 9 10 11 for (int j = 1 ; j <= n; j++) { f[i][j] = f[i - 1 ][j]; if (a[i] == b[j]) { f[i][j] = max (f[i][j], 1 ); for (int k = 1 ; k < j; k++) { if (b[k] < b[j]) { f[i][j] = max (f[i][j], f[i][k] + 1 ); } } } }
可以把 b[j]
替换成 a[i]
,因为上面的 if
判断中保证了 a[i] == b[j]
。
1 2 3 4 5 6 7 8 9 10 11 12 for (int j = 1 ; j <= n; j++) { f[i][j] = f[i - 1 ][j]; if (a[i] == b[j]) { f[i][j] = max (f[i][j], 1 ); for (int k = 1 ; k < j; k++) { if (b[k] < a[i]) { f[i][j] = max (f[i][j], f[i][k] + 1 ); } } } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 int maxv = 1 ;for (int j = 1 ; j <= n; j++) { f[i][j] = f[i - 1 ][j]; if (a[i] == b[j]) { f[i][j] = max (f[i][j], maxv); } if (b[j] < a[i]) { maxv = max (maxv, f[i - 1 ][j] + 1 ); } }
最终得到:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <iostream> using namespace std;const int N = 3010 ;int n;int f[N][N], a[N], b[N];int main () { scanf ("%d" , &n); for (int i = 1 ; i <= n; i++) scanf ("%d" , &a[i]); for (int i = 1 ; i <= n; i++) scanf ("%d" , &b[i]); for (int i = 1 ; i <= n; i++) { int maxv = 1 ; for (int j = 1 ; j <= n; j++) { f[i][j] = f[i - 1 ][j]; if (a[i] == b[j]) f[i][j] = max (f[i][j], maxv); if (b[j] < a[i]) maxv = max (maxv, f[i - 1 ][j] + 1 ); } } int res = 0 ; for (int i = 1 ; i <= n; i++) res = max (res, f[n][i]); printf ("%d\n" , res); return 0 ; }