营销型网站网站设计,南京app开发定制,中国新闻社百度百科,中国建设工程监理协会官方网站计算贡献#xff1b;压缩空间优化时间 传送门#xff1a;$here$ 题意 给出两个字符串$a$,$b$#xff0c;将他们穿插起来#xff08;相对位置不变#xff09;,要求最小化$\sum L(c)$#xff0c;其中$L(c)$的定义时在穿插完的字符串中字符$c$的最大位置与最小位置的…计算贡献压缩空间优化时间 传送门$here$ 题意 给出两个字符串$a$,$b$将他们穿插起来相对位置不变,要求最小化$\sum L(c)$其中$L(c)$的定义时在穿插完的字符串中字符$c$的最大位置与最小位置的差。 数据范围$n \leq 5000$ Solution 问题的转化 根据$LCS$的模型容易想到$dp_{i,j}$表示$a$的前$i$个与$b$的前$j$个穿插后的最小$L$。转移即接$i$或接$b$. 如何转移呢如果要利用这样的状态进行转移肯定需要知道每种字符出现的最早位置。这样的话状态就变得很大了…… 既然用直接的方法无法进行转移那么必须改变计算方法将dp(i,j)的意义改为将a的前i个与b的前j个合并后对最终答案的最优贡献。也就是说不要将dp(i,j)作为子问题去考虑而是考虑这一部分对整体的贡献。 将题目要求的某种字符的最大位置与最小位置的差看做一条线段这条线段从这个字符首次出现开始延伸直到最后一个这种字符出现。那么题目要求最小化的就是26根线段的总长度。那么dp(i,j)就是表示填完a的前i个与b的前j个以后线段的最小总长。 利用DP来解决 要计算最小总长假设现在选择将a[i]放在最后那么就考虑将a[i]填入后总长增加多少很显然对于那些还没有出现完的字符它们对应的线段长度就要1。什么意思对于a[i]前面的每种字符若还有可能在a[i]后方出现那么对应的线段长度需要延伸。如果某种字符在a[i]之后再也不会出现了那就不用延伸了。因此填完a[i]后延伸的总长度就是还没有出现完的字符个数。 值得注意的是这里的dp(i,j)既然不是子问题那是如何保证DP的性质的呢结合深搜来理解一下假设最终字符的最后几位怎么填已经知道那么前面怎么填最优由于之前出现了哪些字符是确定的因此最后几位在填的时候延伸的总长度是确定的那么也就是最小化前面的总长度那么也就是dp(i,j)了。 透过题解看本质 问题的转化 当发现当前问题极难转移时不妨换一种计算思路。既然子问题无法考虑那就整体考虑。 形象生动 把位置之差理解为线段很直观便于思考。避免去空想那些太抽象的东西 。 部分解并不独立有意义 不仅仅是因为这道题部分考虑比较难所以选择整体考虑而是因为这道题的很多部分解对于转移是没有意义的。 my code 值得注意的是如果用二维DP会炸。幸好可以直接滚动数组变成1维。 还发现优化空间能够帮助优化时间。 /*By DennyQi 2019*/
#include cstdio
#include queue
#include cstring
#include algorithm
using namespace std;
typedef long long ll;
const int MAXN 10010;
const int MAXM 20010;
const int INF 0x3f3f3f3f;
inline int Max(const int a, const int b){ return (a b) ? a : b; }
inline int Min(const int a, const int b){ return (a b) ? a : b; }
inline int read(){int x 0; int w 1; register char c getchar();for(; c ^ - (c 0 || c 9); c getchar());if(c -) w -1, c getchar();for(; c 0 c 9; c getchar()) x (x3) (x1) c - 0; return x * w;
}
int T,dp[5010],cnt[5010],lsta[30],lstb[30],fsta[30],fstb[30],la,lb;
char a[5010],b[5010];
inline void Init_cnt(){memset(lsta,0,sizeof(lsta));memset(lstb,0,sizeof(lstb));memset(fsta,0x3f,sizeof(fsta));memset(fstb,0x3f,sizeof(fstb));for(int i 1; i la; i){lsta[a[i]-A] max(lsta[a[i]-A],i);fsta[a[i]-A] min(fsta[a[i]-A],i);}for(int i 1; i lb; i){lstb[b[i]-A] max(lstb[b[i]-A],i);fstb[b[i]-A] min(fstb[b[i]-A],i);}
}
inline void DP(){memset(dp,INF,sizeof(dp));memset(cnt,0,sizeof(cnt));char cur;dp[0] 0;for(int i 0; i la; i){for(int j 0; j lb; j){if(i0 j0) continue;if(i 0){ cnt[j] cnt[j-1];cur b[j]-A;if(j fstb[cur]) cnt[j];if(j lstb[cur] lsta[cur] 0) --cnt[j];}else{cur a[i]-A;if(j lstb[cur] i lsta[cur]) --cnt[j];if(j fstb[cur] i fsta[cur]) cnt[j];}dp[j] min((j0)?INF:dp[j-1], (i0)?INF:dp[j])cnt[j];}}
}
int main(){scanf(%d,T);while(T--){scanf(%s%s,a1,b1);la strlen(a1), lb strlen(b1);Init_cnt();DP();printf(%d\n,dp[lb]);}return 0;
} 转载于:https://www.cnblogs.com/qixingzhi/p/10390174.html
