首页 > 代码库 > Educational CF # 17 C 二分,字符串 D 最长路,dp

Educational CF # 17 C 二分,字符串 D 最长路,dp

Educational Codeforces Round 17

C. Two strings

题意:两个字符串A,B,从B中删除尽可能少的子串,要使得B剩下的字符串是A的子序列,输出B剩下的字符串。(注意子串与子序列区别)

总结:看了某神犇的代码,不太理解。。官方题解:不要去想从B中删掉子串,应该想,从B的左端取出一段子串,再从右端取出一段子串。

技术分享
//     Educational Codeforces Round 17  C
#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define F(i,a,b)  for (int i=a;i<b;i++)
#define FF(i,a,b) for (int i=a;i<=b;i++)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 1e5+10;

char a[N], b[N];
int fl[N], fr[N];

int main()
{
    int la, lb, i, j, mid, l, r, a1, a2;
    scanf("%s%s", a+1, b+1);
    la=strlen(a+1), lb=strlen(b+1);
    for(i=1, fl[0]=j=0; b[i]; ++i) {
        for(++j; j<=la&&a[j]!=b[i]; ++j) ;
        fl[i]=j;
    }
    for(i=lb, fr[lb+1]=j=la+1; b[i]; --i) {
        for(--j; j>0&&a[j]!=b[i]; --j) ;
        fr[i]=j;
    }
    for(l=0, r=lb; l<=r; ) {
        mid=l+r>>1;
        for(i=0; i+mid<=lb; ++i) {
            if(fl[i]<fr[i+mid+1]) break;    //
        }
        if(i+mid<=lb) a1=i, a2=i+mid+1, r=mid-1;
        else l=mid+1;
    }
    for(i=1; i<=a1; ++i) putchar(b[i]);
    for(i=a2; b[i]; ++i) putchar(b[i]);
    if(a2-a1>lb) putchar(-);

    return 0;
}
View Code

D. Maximum path

题意:给出3行n列的格子,每个格子有一个权值。要从左上角到右下角,每个格子最多走一次,求最大路径和。

总结:类似插头dp,还要讨论,不会。。

Educational CF # 17 C 二分,字符串 D 最长路,dp