回 帖 发 新 帖 刷新版面

主题:[讨论]TJU1050 - 单词的划分

这是一道比较入门的动态规划,现在发现人气不旺就拿过来大家讨论一下吧。
TJU1050: http://acm.tongji.edu.cn/people/ps/showproblem.php?problem_id=1050

我是这样想的:

一个一维的状态数组,以每个字母划分。f[i] 表示前 i 个字母最少分的份数。
那么相应的状态转换方程就是
  f[i] = f[i - lengthof(words[v]] + 1, f[0] = 0;
当然还要判断一下那个中间的东西是不是 words[v] 的内容
且 f[i] = 0 (i 不等于 0) 不能参加运算.

大家看看题去吧,把自己的想法放到这里!

回复列表 (共3个回复)

沙发

你这个方程不对吧

f[i]=min(f[i-length(word[j])]+1)  s[i-length(word[j])+1]~s[i]=word[j]
1<=i<=length(s),1<=j<=n
初值f[0]=0,f[i]=maxint(i>=1)
这样才对吧

至少我这样ac.
你的连min或者max都没有,至少不算动态规划。。。而且如果不求最小,还是错的

板凳

反正就是这个意思,每个单词都要过一遍,其中的 min 还是有的,就是没写而已。

3 楼

我faint
既然说是dp题,却没有opt……

我来回复

您尚未登录,请登录后再回复。点此登录或注册