题目来源:http://acm.pku.edu.cn/JudgeOnline/problem?id=1836
解题报告:
设各个成员的身高的数组为h[0...n-1],n为总人数。要满足题目条件,对0<=i<n,不妨设d[i]代表h[i]左边满足条件(即身高递增)的排列中可以安排的最多的人数,p[i]代表h[i]右边满足条件(即身高递减)的排列中可以安排的最多的人数。
则有递推式:
d[i]=max(d[k1]+1, d[k2]+1, ...., d[kt]+1),其中kj<i, 且h[kj]<h[i],(1<=j<=t)
p[i]=max(p[k1]+1, p[k2]+1, ...., p[kt]+1),其中kj>i, 且h[kj]<h[i],(1<=j<=t)
可以根据d[], p[]求得相应的最优解。
这道题一开始WA了,有一个特殊情况没有考虑进去,用以下数据测试:
8
3 4 5 1 2 5 4 3
答案是:2
这组数据的排列情况应为3 4 5 5 4 3,虽然5 5的身高一样,但仍能满足条件,我一开始没有考虑到这种情况。
int main()
{
int n;
cin >> n;
double *h=new double[n];
int *d=new int[n];
int *p=new int[n+1];
for(int i=0;i<n;i++)
{
cin >> h[i];
d[i]=1;
p[i]=1;
}
p[n]=0;
for(int i=1;i<n;i++)
{
for(int k=0;k<i;k++)
if(h[i]>h[k])
d[i]=max(d[i],d[k]+1);
}
for(int i=1;i<n;i++)
d[i]=max(d[i],d[i-1]);
for(int i=n-1;i>=0;i--)
{
for(int k=n-1;k>i;k--)
if(h[i]>h[k])
p[i]=max(p[i],p[k]+1);
}
for(int i=n-1;i>=0;i--)
p[i]=max(p[i],p[i+1]);
int m=p[1]+d[0];
for(int i=1;i<n;i++)
{
if(m < p[i+1]+d[i])
m=p[i+1]+d[i];
}
cout << n-m << endl;
}
附录:
Time Limit: 1000MS | Memory Limit: 30000K | |
Total Submissions: 4265 | Accepted: 1306 |
Description
Write a program that, knowing the height of each soldier, determines the minimum number of soldiers which have to get out of line.
Input
There are some restrictions:
• 2 <= n <= 1000
• the height are floating numbers from the interval [0.5, 2.5]
Output
Sample Input
8 1.86 1.86 1.30621 2 1.4 1 1.97 2.2
Sample Output
4