哈尔滨餐饮加盟网站建设,栾城网站制作,数字营销策划方案,怎么推广自己的产品Powered by:NEFU AB-IN
Link 文章目录 482. 合唱队形题意思路代码 482. 合唱队形 题意 略 #xff08;形成山丘式的队形#xff0c;最少提几个人#xff09; 思路 前后各做一次LIS#xff08;必须是dp#xff09; f[i] 就表示以i为结尾的正序的LIS g[i] 就表示以i为结尾的…Powered by:NEFU AB-IN
Link 文章目录 482. 合唱队形题意思路代码 482. 合唱队形 题意 略 形成山丘式的队形最少提几个人 思路 前后各做一次LIS必须是dp f[i] 就表示以i为结尾的正序的LIS g[i] 就表示以i为结尾的逆序的LIS 代码 #include bits/stdc.h
using namespace std;
#define int long long
#undef int#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS \ios::sync_with_stdio(false); \cin.tie(nullptr); \cout.tie(nullptr)
#define DEBUG(X) cout #X : X \nconst int N 1e5 10, INF 0x3f3f3f3f;int a[N], f[N], g[N];signed main() {//freopen(Tests/input_1.txt, r, stdin);IOS;int n;cin n;for (int i 1; i n; i) cin a[i];for (int i 1; i n; i) {f[i] 1;for (int j 1; j i; j) {if (a[j] a[i]) f[i] max(f[i], f[j] 1);}}for (int i n; i; -- i) {g[i] 1;for (int j n; j i; -- j)if (a[j] a[i]) g[i] max(g[i], g[j] 1);}int mx 0;for (int i 1; i n; i) {mx max(mx, f[i] g[i] - 1);}cout n - mx;return 0;
}
