poj1836 Alignment
这题对题意的理解是一个关键。一开始以为是求最大递增序列或最大递减序列，然后看discuss，发现是求一个序列，该序列中有一个最大值max，然后从0到max是递增的，然后max+1到n-1是递减的。一开始的时候，用了超级暴力的dp，然后tle了，之后发现可以通过预处理来减少时间耗费。先分别从0到n-1和n-1到0求出LIS。之后枚举中间最大值，求出相应的那个序列的长度，再从所有长度中求出最大值，这个值就是最长的符合要求的序列。最后就只要用n减去那个数，就是要出列的人数了。
后记：
1.LIS的状态转移方程很经典，要记住～～！！！
2.给出一些数据：
Sample Input
8
1.86 1.86 1.30621 2 1.4 1 1.97 2.2
12
0.9 0.8 0.7 1 0.6 0.5 1.1 1.2 1.3 1.4 1.5 1.6
5
1 1 1 1 1
5
1 1.5 2 1.5 1
8
3 4 5 1 2 5 4 3
Sample Output
4
4
3
0
2
＝＝＝＝＝＝＝＝＝＝＝＝分割线＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
#include <iostream>
using namespace std;
float h[1001];
int d[2][1001], n;
void LIS()
{
int i, j;
for (i = 0; i < n; i++)
for (j = 0; j < i; j++)
if (h[j] < h[i]) d[0][i] = d[0][i] < d[0][j] + 1 ? d[0][j] + 1 : d[0][i];
}
void LDS()
{
int i, j;
for (i = n - 1; i >= 0; i--)
for (j = n - 1; j > i; j--)
if (h[j] < h[i]) d[1][i] = d[1][i] < d[1][j] + 1 ? d[1][j] + 1 : d[1][i];
}
int main()
{
int i, j, tmp, maximum, lis, lds;
while (cin >> n)
{
for (i = 0; i < n; i++) scanf("%f", &h[i]);
//dp
for (i = 0; i < n; i++) d[0][i] = d[1][i] = 1;
LIS();
LDS();
for (lis = 0, maximum = 2, i = 0; i < n; i++)
{
lis = lis > d[0][i] ? lis : d[0][i];
for (lds = 0, j = i + 1; j < n; j++)
lds = lds > d[1][j] ? lds : d[1][j];
tmp = lis + lds;
maximum = maximum > tmp ? maximum : tmp;
//test
// cout << i << " " << lis << " && " << lds << endl;
}
maximum = n - maximum;
cout << maximum << endl;
}
return 0;
}
using namespace std;
float h[1001];
int d[2][1001], n;
void LIS()
{
int i, j;
for (i = 0; i < n; i++)
for (j = 0; j < i; j++)
if (h[j] < h[i]) d[0][i] = d[0][i] < d[0][j] + 1 ? d[0][j] + 1 : d[0][i];
}
void LDS()
{
int i, j;
for (i = n - 1; i >= 0; i--)
for (j = n - 1; j > i; j--)
if (h[j] < h[i]) d[1][i] = d[1][i] < d[1][j] + 1 ? d[1][j] + 1 : d[1][i];
}
int main()
{
int i, j, tmp, maximum, lis, lds;
while (cin >> n)
{
for (i = 0; i < n; i++) scanf("%f", &h[i]);
//dp
for (i = 0; i < n; i++) d[0][i] = d[1][i] = 1;
LIS();
LDS();
for (lis = 0, maximum = 2, i = 0; i < n; i++)
{
lis = lis > d[0][i] ? lis : d[0][i];
for (lds = 0, j = i + 1; j < n; j++)
lds = lds > d[1][j] ? lds : d[1][j];
tmp = lis + lds;
maximum = maximum > tmp ? maximum : tmp;
//test
// cout << i << " " << lis << " && " << lds << endl;
}
maximum = n - maximum;
cout << maximum << endl;
}
return 0;
}
评论 (0)