目录
Alignment （DP基础--最长上升子序列）
题目题意思路代码
Alignment （DP基础--最长上升子序列）
题目
poj1836
题意
删除一些数，使得中间的每个数都比左边或者右边的大。
思路
从左边进行一次LIS,然后从右边进行一次，记录的数组分别为a,b。然后枚举中间的两个数为两个LIS的终点，求出最大值，其为留下来的人,总数减去即可。
代码
#include <algorithm>
#include <iostream>
#include <cstring>
#define N 1003
using namespace std;
double a[N];
int d[N], b[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)//从左边进行LIS 结果设为 d
{
d[i] = 1;
for (int j = 0; j <= i; j++)
{
if (a[i] > a[j])
{
d[i] = max(d[i], d[j] + 1);
}
}
}
for (int i = n - 1; i >= 0; i--)//从右边进行LIS 结果设为b
{
b[i] = 1;
for (int j = n - 1; j >= i; j--)
{
if (a[i] > a[j])
{
b[i] = max(b[i], b[j] + 1);
}
}
}
int res = 0;
for (int i = 0; i < n; i++)//往中间枚举
for (int j = i+1; j < n; j++)
{
res = max(res, d[i] + b[j]);
}
cout << n-res;
}
转载于:https://www.cnblogs.com/tttfu/p/11244158.html
相关资源：JAVA上百实例源码以及开源项目
