网站做简介,精品故事网,营销型平台网站建设,建筑室内设计主要学什么题意#xff1a;给定两个长度分别为n和m 的颜色序列#xff0c;要求按顺序合并成一个序列#xff0c;即每次可以把开头的颜色放到新序列末尾#xff0c;跨度l#xff08;c#xff09;等于最大和最小的位置之差。 思路#xff1a;递推#xff0c;f#xff08;i,j#…题意给定两个长度分别为n和m 的颜色序列要求按顺序合并成一个序列即每次可以把开头的颜色放到新序列末尾跨度lc等于最大和最小的位置之差。 思路递推fi,j表示s1移走了i个元素s2移走了j个元素的状态g[i][j]表示当前还有多少个颜色是已经出现但尚未结束状态)状态转移方程f[i][j]min(f[i][j1])g[i][j]比较蛋疼的是对原来串化成g的处理。 code #include iostream
#include cstdio
#include cmath
#include algorithm
#include cstring
#include sstream
#include string
#include vector
#include list
#include queue
#include stack
#include map
#include set
#include bitsetusing namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;const int INF0x3fffffff;
const int inf-INF;
const int N5005;
const int M2005;
const int mod1000000007;
const double piacos(-1.0);#define cls(x,c) memset(x,c,sizeof(x))
#define cpy(x,a) memcpy(x,a,sizeof(a))
#define ft(i,s,n) for (int is;in;i)
#define lson l,m,rt1
#define rson m1,r,rt1|1
#define lrt rt1
#define rrt rt1|1
#define middle int m(rl)1
#define lowbit(x) (x-x)
#define pii pairint,int
#define mk make_pair
#define IN freopen(in.txt,r,stdin);
#define OUT freopen(out.txt,w,stdout);char s[N];
int len[2],a[2][N];
int f[N][N];
int ft[2][26],lt[2][26],g[N][N];
void sol()
{cls(ft,0);cls(lt,0);ft(i,0,1) ft(j,1,len[i]){if (!ft[i][a[i][j]]) ft[i][a[i][j]]j;lt[i][a[i][j]]j;}ft(i,1,len[0]){g[i][0]g[i-1][0];if (ft[0][a[0][i]]i) g[i][0];if (lt[0][a[0][i]]i!lt[1][a[0][i]]) g[i][0]--;}ft(i,0,len[0]) ft(j,1,len[1]){g[i][j]g[i][j-1];if (ft[1][a[1][j]]j(!ft[0][a[1][j]]||ft[0][a[1][j]]i)) g[i][j];if (lt[1][a[1][j]]j[0][a[1][j]]i) g[i][j]--;}
}
int main()
{int T;scanf(%d,T);while (T--){ft(i,0,1){scanf(%s,s1);len[i]strlen(s1);ft(j,1,len[i]) a[i][j]s[j]-A;}sol();ft(i,1,len[0]) f[i][0]f[i-1][0]g[i-1][0];ft(i,1,len[1]) f[0][i]f[0][i-1]g[0][i-1];ft(i,1,len[0]) ft(j,1,len[1])f[i][j]min(f[i-1][j]g[i-1][j],f[i][j-1]g[i][j-1]);printf(%d\n,f[len[0]][len[1]]);}
}
