Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
此题目求含有的最大可匹配字符串数目,然后L-Max就是答案了f[0] = 0; FORi(1,L+1,1) { f[i] = f[i-1]; FORj(0,W,1) { if( len[j]<=i ) { if( dic[j][len[j]-1]==in[i-1]) { r1 = i-1; r2 = len[j]-1; while(r1>=0 && r2>=0) { if( dic[j][r2]==in[r1]) r2--; r1--; } if(r2<0) {//find it if(r1<0) { //f[i] = TMIN(f[i],i-len[j]); f[i] = TMAX(f[i],len[j]); } else { //f[i] = TMIN(f[i],i-1-r1-len[j] + f[r1+1]); f[i] = TMAX(f[i],len[j]+f[r1+1]); } } } } } } 注释掉的是按照对于每个位置,可删除的最小字符数量,然后答案就是f[L] 非注释掉的是按照对于每个位置,可匹配的最大字符数量,然后总数L-f[L] 这两种方法都可以过,有区别吗? Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator