首页 > 代码库 > 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; }
D. Maximum path
题意:给出3行n列的格子,每个格子有一个权值。要从左上角到右下角,每个格子最多走一次,求最大路径和。
总结:类似插头dp,还要讨论,不会。。
Educational CF # 17 C 二分,字符串 D 最长路,dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。