牛顿法求解无约束问题这个题，第二题

来源：蜘蛛抓取(WebSpider) 时间：2017-09-05 14:48 标签： kkt条件例题求解
2511人阅读
动态规划（14）
正式赛（5）
直接讲100分的算法。
动态规划。
F[i][j][l]表示B[1~i]已经匹配完了A[1~j]，一共分成了l个字符串。
转移有两种情况。
这种情况下，我们需要新开一个子串来容纳Bi。
我们可以跟着上一次匹配的位置匹配，这样不需要开多一个新子串。
故转移方程为：
F[i][j][l]=f[i-1][1~(j-1)][l-1]+f[i-1][j-1][l];
注意事项：
&1&如果Bi≠Aj，则F[i][j][l]只能等于0。
&2&F[i-1][1~(j-1)][l-1]这一段和可以维护以下，时间复杂度时间复杂度的次数由4降为3，不会超时。
&3&不会超时但如果直接开三维数组会爆空间。考虑到F[i]只会由F[i-1]转移过来，可以开一个滚动数组。
Code(pascal)
cha,chb:array[1..1000] of
f:array[0..1,-10..1000,-10..200] of
n,m,j,k,l,i,o,p,la,lb,u,ans:
assign(input,'substring.in'); reset(input);
assign(output,'substring.out'); rewrite(output);
readln(la,lb,m);
for i:=1 to la do
read(cha[i]);
for i:=1 to lb do
read(chb[i]);
for i:=1 to la do
if cha[i]=chb[1] then f[0,i,1]:=1;
for l:=2 to lb do
u:=(o+1) mod 2;
for j:=1 to m do
for i:=1 to la do
p:=(p+f[o,i-1,j-1]) mod
if cha[i]=chb[l] then f[u,i,j]:=(f[o,i-1,j]+p) mod maxn
else f[u,i,j]:=0;
for i:=1 to la do
ans:=(ans+f[o,i,m]) mod
writeln(ans);
close(input);
close(output);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：243324次
积分：3319
积分：3319
排名：第10353名
原创：111篇
评论：32条
Swimming in the
Sea of Questions
~~O(∩_∩)O~~
阅读：14232

我要回帖

更多关于 kkt条件例题求解 的文章

 

随机推荐