[其他] [已解决]批处理删除给定数字串的一部分使剩余数字升序或降序排列

基拉freedom

偶尔看到这一个问题
例子：

1 2 55 3 4 5 1 7 8 9 
然后结果是 
删去 55 1
或者直接给出排列好的数列 1 2 3 4 5 7 8 9
复制代码

如果用数直接比对以前的数 那效率一定很低 这里求代码的简约 高效
大家有什么好的方案
注：
数字不能换位子
例如 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或其他的
加深的：
找出删去数最少 也就是令这个升序数组最长的答案

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

Seter

回楼上,本来set/ai+=1放下面的,但忘记改了...所以没注意到...

基拉freedom

因为
l1和r1的值为空 比较后 赋的值的也是空
不知道这样理解有没有错

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
复制代码

你改的是第二个for,1,1,!i!改成2,1,!i!-1了吧
i-1可以明白,但为什么要从2循环起呢?

基拉freedom

裁开的代码
中间觉得多余的地方改了改 不知道有没有改错：

@echo off&setlocal enabledelayedexpansion
set/pk=
set i=1
for %%i in (%k%) do (
set/a i+=1
set m=0
set r=
for /l %%j in (2,1,!i!-1) 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
)
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
复制代码

基拉freedom

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

Seter

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

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

基拉freedom

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

Seter

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

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

其实思路很简单
假设数据为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

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

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

Seter

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

应该得:
1 2 3
1 5 6

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

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

slore

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

应该得:
1 2 3
1 5 6

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

基拉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 编辑 ]