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%!&pauseCOPY

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

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

Seter

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

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)暂时为0COPY

要知道最后的字符串加个变量就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%&pauseCOPY

348B....

Seter

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

Seter

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

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

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%
pauseCOPY

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

Seter

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