普通DP|【BZOJ1609】[Usaco2008 Feb]Eating Together麻烦的聚餐【最长不下降子序列】
【普通DP|【BZOJ1609】[Usaco2008 Feb]Eating Together麻烦的聚餐【最长不下降子序列】】【题目链接】
正反做一次最长不下降子序列，显然答案是n减去最长不下降子序列的长度。
/* Footprints In The Blood Soaked Snow */
#include
#include using namespace std;
const int maxn = 30005, inf = 0x3f3f3f3f;
int n, num[maxn], dp[maxn], g[maxn];
inline int iread() {
int f = 1, x = 0;
char ch = getchar();
for(;
ch < '0' || ch > '9';
ch = getchar()) f = ch == '-' ? -1 : 1;
for(;
ch >= '0' && ch <= '9';
ch = getchar()) x = x * 10 + ch - '0';
return f * x;
}inline int calc() {
int ans = 0;
for(int i = 1;
i <= n;
i++) g[i] = inf;
for(int i = 1;
i <= n;
i++) {
int k = upper_bound(g + 1, g + 1 + n, num[i]) - g;
dp[i] = k;
g[k] = num[i];
ans = max(ans, dp[i]);
}
return n - ans;
}int main() {
n = iread();
for(int i = 1;
i <= n;
i++) num[i] = iread();
int ans = n;
ans = min(ans, calc());
reverse(num + 1, num + 1 + n);
ans = min(ans, calc());
printf("%d\n", ans);
return 0;
}
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长