AcWing 187 导弹防御系统 暴搜

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;const int N = 200010, mod = 1e9 + 7;int n, m, k, x, y, z, ans, t, depth;
int w[N], f[N];
int up[N], down[N];bool dfs(int depth, int u, int su, int sd)
{if (su + sd > depth) return false;if (u == n + 1) return true;bool flag = false;for (int i = 1; i <= su; i ++ ){if (up[i] < w[u]){flag = true;int temp = up[i];up[i] = w[u];if(dfs(depth, u + 1, su, sd)) return true;up[i] = temp;break;}}if (!flag){up[su + 1] = w[u];if (dfs(depth, u + 1, su + 1, sd)) return true;}flag = false;for (int i = 1; i <= sd; i ++ ){if (down[i] > w[u]){flag = true;int temp = down[i];down[i] = w[u];if (dfs(depth, u + 1, su, sd)) return true;down[i] = temp;break;}}if (!flag){down[sd + 1] = w[u];if (dfs(depth, u + 1, su, sd + 1)) return true;}return false;
}void solve()
{while (cin >> n, n){for (int i = 1; i <= n; i ++ )cin >> w[i];depth = 0;while (!dfs(depth, 1, 0, 0)) depth ++;cout << depth << "\n";}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;
//	cin >> T;while (T -- ){solve();}
}