bhsx

例如 1 2 3 4 5 6 10 9
答案应为 1 2 3 4 5 6 9
而不是1 2 3 4 5 6 9 10
8L的说得对
基础的 那只要求以第一个数为基准 给出一种答案就可以了 但升序的数组不可以有遗留哦
也就是本来可以1 2 3 4 5 6 9的 不能少数字 变成 1 3 4 5 6 9或其他的

1 2 3 4 5 6 10 也行??

[ 本帖最后由 bhsx 于 2009-10-2 17:53 编辑 ]

Seter

同样的题目我用C做过,使用DP算法完美解决...我去温习下看看能不能做...

Seter

@setlocal enabledelayedexpansion&set/pk=&set i=1
@for %%i in (%k%) do @set/ai+=1&set m=0&set r=&(@for /l %%j in (1,1,!i!) do @if !e%%j! lss %%i if !m! lss !l%%j! set m=!l%%j!&set r=!r%%j!)&set r!i!=!r! %%i&set/a l!i!=m+1&set e!i!=%%i
@echo!r%i%!&pause
复制代码

253B[最近疯狂于文本缩减]

[ 本帖最后由 Seter 于 2009-10-2 20:45 编辑 ]

Seter

嘿嘿,多谢基拉大大...考验你手工分段的时候到了!

基拉freedom

恩
分割好了
还要慢慢理解
代码有点不太完美 不过也差不多了
很是感谢 这个问题是偶尔从书中找到的 只要叫我们自己找找
测试了一下
23 12 14 15 16 17 18 19 4564 213 456 123 456 789 56 231
12 14 15 16 17 18 19 213 231
最长的数列其实应为
12 14 15 16 17 18 19 123（或213） 456 789

基拉freedom

思路看懂了
看来代码必须多研究才可以
再次说声谢谢 你的代码是找此数列中大小相近（我也说不大清楚）的数列吧 很不错的思路
分割好的：

@echo off&setlocal enabledelayedexpansion
set/p k=请输入数字:
set i=1
for %%i in (%k%) do (
set /a i+=1
set m=0
set "r="
for /l %%j in (1,1,!i!) do (
if !e%%j! lss %%i if !m! lss !l%%j! set m=!l%%j!&set "r=!r%%j!"
)
set "r!i!=!r! %%i"
set/a "l!i!=m+1"
set e!i!=%%i
)
@echo !r%i%!
pause
复制代码

[ 本帖最后由 基拉freedom 于 2009-10-2 21:24 编辑 ]

slore

貌似都不全。。。
1 5 2 6 3

应该得:
1 2 3
1 5 6

有得全解的思路，懒的写了。。。bat操作数组不好，不方便。

Seter

原帖由 slore 于 2009-10-2 23:23 发表
貌似都不全。。。
1 5 2 6 3

应该得:
1 2 3
1 5 6

有得全解的思路，懒的写了。。。bat操作数组不好，不方便。

只求单解嘛,否则太麻烦...批中用不了数据结构的,

Seter

SORRY,我的代码有问题!
输入数据的最后那个数字不一定要使用...

[ 本帖最后由 Seter 于 2009-10-3 08:28 编辑 ]

Seter

其实思路很简单
假设数据为a(1),a(2),a(3),...a(k)
到a(i)的最长长度为MaxLen(i)
则

MaxLen(1)=1
MaxLen(i)=Max{MaxLen(1),MaxLen(2),...MaxLen(i-1)}+1
MaxLen(1)至MaxLen(i-1)中,若a(j)>a(i),则不计入,即MaxLen(j)暂时为0
复制代码

要知道最后的字符串加个变量就OK了(我加r1,r2,r3...的)

[ 本帖最后由 Seter 于 2009-10-3 08:17 编辑 ]

Seter

@echo off&setlocal enabledelayedexpansion&set/pk=&set i=1
(for %%i in (%k%) do set/ai+=1&set m=0&set r=&(for /l %%j in (1,1,!i!) do if !e%%j! lss %%i if !m! lss !l%%j! set m=!l%%j!&set r=!r%%j!)&set r!i!=!r! %%i&set/al!i!=m+1&set e!i!=%%i)&set m=!l1!&set r=!r1!&for /l %%i in (2,1,!i!) do if !m! lss !l%%i! set m=!l%%i!&set r=!r%%i!
echo%r%&pause
复制代码

348B....

Seter

来个小水
基拉大大不会是大学生吧...
刚找到这题了,不过不是批的,是浙江大学的网络ACM的一道题,Longest Ordered Subsequence(http://acm.zju.edu.cn/ 网上第2136题)
咳咳...大学生水平也不过如此...

基拉freedom

回27楼的.......我才高中 只是对这种算法好奇而已
我还得多学习多学习

Seter

回28楼的,高中也比我大啊....这个东西我一开始也做不出来,后来看了本DP(动态规划)的书就豁然开朗了...

MaxLen(k)的值,就是在a(k)左边,重点数值小于a(k),且长度最大的那个上升子序列的长度再加1.因为a(k)左边任何终点小于a(k)的子序列,加上a(k)后就能形成一个更长的子序列
复制代码

基拉freedom

哎
我再想想
DP没学过 算法接触很少 现在连个回溯都搞不清楚 惭愧啊 惭愧