解题思路:
注意事项:
参考代码:
#include<iostream> #include<cmath> using namespace std; int num[1010];//每个人的身高 int ans=1;//最后留下的人数 int sum1[1010],sum2[1010];//升序列和降序列中留下的人数 int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>num[i];//输入 sum1[i]=1;//留下的人数,至少为1 sum2[i]=1;} for(int i=1;i<=n;i++) for(int j=1;j<i;j++) if(num[i]>num[j])//如果i位置的值大于j位置的,这是可以作为上升子序列 sum1[i]=max(sum1[i],sum1[j]+1);//比较不取i位置和取i位置哪个留下的人多 for(int i=n;i>=1;i--)//最小降序列,反着枚举 for(int j=n;j>i;j--) if(num[i]>num[j]) sum2[i]=max(sum2[i],sum2[j]+1); for(int i=1;i<=n;i++) ans=max(ans,(sum2[i]+sum1[i]-1));//ans是留下的人数,和每一种方案留下的人数比较。减一是中间的人重复计数。 cout<<n-ans<<endl;//n是总人数,ans留下的人数 return 0; }
0.0分
1 人评分
C二级辅导-统计字符 (C语言代码)浏览:483 |
C语言程序设计教程(第三版)课后习题6.9 (C++代码)浏览:528 |
C语言程序设计教程(第三版)课后习题6.11 (C语言代码)浏览:473 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:539 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:635 |
高精度加法 (C++代码)(大数加法)浏览:917 |
C二级辅导-进制转换 (C语言代码)浏览:615 |
c primer plus 第十二章 12.1小节浏览:377 |
成绩转换 (C语言代码)浏览:1005 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:704 |