高考问答济南机关单位招聘客服:求教一个动态规划问题~用PASCAL语言做
来源：百度文库 编辑：高考问答 时间：2024/04/28 07:17:09
农场实习farm
[问题描述]
公益劳动回来之后，小可可又进入了第二阶段的毕业实习。这次小可可被安排去农场劳动。
农场的小河边上沿着河岸长了很多西瓜，小可可和一个老师的任务就是去摘西瓜。
老师又一个摘西瓜的怪癖：总是沿着河岸边走边摘，第一个被摘西瓜是哪一个完全凭老师高兴了，没有什么固定规则，但以后摘的每一个西瓜都不能比上一个小。
例如，沿河岸有4个西瓜，大小依次是3、6、2、4。
如果老师首先摘的是第一个西瓜（3），则他们能摘的大小为3、6或3、4的西瓜。
如果首先摘的是第二个西瓜 ，则他们只能摘这个西瓜……
现在知道了沿河岸各个西瓜的大小，你能算出老师和小可可沿着河岸走一遍之后，至少有多少个西瓜被遗漏而不能摘下来吗？
[输入]第一个数是西瓜的个数c(c<=10的6次方），随后的c个数依次是沿着河岸的各个西瓜大小（各个西瓜的大小都不能超过10的8次方）
[输出]输出遗漏不能摘的西瓜个数最小值u（u<=1000)。
[例如]
输入
4 3 6 2 4
输出
2
那个高手能将这道题用动态规划做出来啊！~~PASCAL语言来做！谢啦！
[问题描述]
公益劳动回来之后，小可可又进入了第二阶段的毕业实习。这次小可可被安排去农场劳动。
农场的小河边上沿着河岸长了很多西瓜，小可可和一个老师的任务就是去摘西瓜。
老师又一个摘西瓜的怪癖：总是沿着河岸边走边摘，第一个被摘西瓜是哪一个完全凭老师高兴了，没有什么固定规则，但以后摘的每一个西瓜都不能比上一个小。
例如，沿河岸有4个西瓜，大小依次是3、6、2、4。
如果老师首先摘的是第一个西瓜（3），则他们能摘的大小为3、6或3、4的西瓜。
如果首先摘的是第二个西瓜 ，则他们只能摘这个西瓜……
现在知道了沿河岸各个西瓜的大小，你能算出老师和小可可沿着河岸走一遍之后，至少有多少个西瓜被遗漏而不能摘下来吗？
[输入]第一个数是西瓜的个数c(c<=10的6次方），随后的c个数依次是沿着河岸的各个西瓜大小（各个西瓜的大小都不能超过10的8次方）
[输出]输出遗漏不能摘的西瓜个数最小值u（u<=1000)。
[例如]
输入
4 3 6 2 4
输出
2
那个高手能将这道题用动态规划做出来啊！~~PASCAL语言来做！谢啦！
偶先说一下算法，程序过一会再贴出来。
这道题是“最长不上升子序列”问题：
设f[i]表示以第i个西瓜为第一个西瓜所能带来的最大收益，显然有
f[i]=max{f[j]+1)(i<j<=n,v[j]<=v[i])
f[n]=1;
则最大收益maxn＝max{f[i]}(1<=i<=n)
答案ans=n-maxn;