[CF1310C] Au Pont Rouge
首先，肯定要将所有的代价给弄出来，若先不管划分段数的限制，那么所有代价就是\(S\)的所有字串
那么字串的数量也就是\(\frac{n*(n+1)}{2}\)，约为\(10^6\)的范围
既然答案要求一个准确的字符串，所以考虑二分答案，首先对所有的代价进行排序（\(lcp\)轻松搞定）
对于当前二分的字符串\(s_{now}\)，check函数内用dp进行判断
\(dp[i][j]\)为\(s[i,n]\)，划分成\(j\)段的方案数
\]
复杂度是\(O(n^3)\)的，所以想办法把这个\(k\)做掉
后面这个\(\sum_{k>i\&\&s[i,k-1]\geqslant s_{now}} dp[k][j-1]\)显然是一个后缀和可以\(O(1)\)解决的
对于字符串\(a,b\)，设\(a[1,i-1]==b[1,i-1]\&\&a[i]!=b[i]\ \ (i<min(len_a,len_b))\)
若\(a[1,i]>b[1,i]\)，则对于\(a\)的每个结尾处\(\geqslant i\)的前缀，其字典序都大于\(b\)
否则，\(a\)的所有前缀的字典序都小于\(b\)
然后，距离做掉\(k\)还差一部，就是如何\(O(1)\)找到第一个\(k\)
这时，就又可以上\(lcp\)了
设\(t\)为\(min\{s[i,n]与s_{now}的lcp，len_{s_{now}}\}\)
当\(t==len_{s_{now}}\)或者\(s_{now}\)的第\(t+1\)个字符小于\(s[i+t]\)时，第一个\(k\)就是\(t+1\)
否则，就不存在\(k\)（见上面注释起来的文字说明）
然后，就完了
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e3+5;
int n,m,lcp[N][N],l,r,mid,cnt;
ll k;
char s[N];
struct fk{
int l,r;
}a[N*N];
bool cmp(fk a,fk b){
int t=lcp[a.l][b.l];
if(t>=a.r-a.l+1||t>=b.r-b.l+1) return a.r-a.l+1<b.r-b.l+1;
return s[a.l+t]<s[b.l+t];
}
ll dp[N][N],sum[N][N];
bool check(int now){
memset(dp,0,sizeof(dp)),memset(sum,0,sizeof(sum));
sum[n+1][0]=1;
for(int i=n;i;--i){
int t=min(a[now].r-a[now].l+1,lcp[i][a[now].l]);
if(t==a[now].r-a[now].l+1||s[a[now].l+t]<s[i+t]) for(int j=1;j<=m;++j) dp[i][j]=sum[i+t+1][j-1];
for(int j=0;j<=m;++j) sum[i][j]=min(sum[i+1][j]+dp[i][j],k);
}
return dp[1][m]>=k;
}
int main(){
scanf("%d%d%lld",&n,&m,&k);
getchar(); for(int i=1;i<=n;++i) scanf("%c",&s[i]);
for(int i=n;i;--i)
for(int j=n;j;--j){
if(s[i]==s[j]) lcp[i][j]=lcp[i+1][j+1]+1;
if(j>=i) a[++cnt]=fk{i,j};
}
sort(a+1,a+cnt+1,cmp);
l=1,r=cnt;
while(l<=r){
mid=l+r>>1;
if(check(mid)) l=mid+1;
else r=mid-1;
}
for(int i=a[l].l;i<=a[l].r;++i) printf("%c",s[i]);
return 0;
}
[CF1701E] Text Editor
可以将\(s\)划分成三段
一段为从左往右删（可为空），一段为不删，一段为从右向左删（可为空）
那么操作的整体流程就是：从右向左删，遇到不删的区域，跳到左边去，然后从左往右删，遇到不删的区域，结束
根据这个方法，可以先定义出一个三位dp
\(dp[i][j][0/1/2]\)，\(t[i]\)与\(s[j]\)匹配（可以是对应关系，也可以是\(s[j]\)被删掉）
\]
\]
\]
然后就是因为\(1\leqslant len_t\leqslant len_s\leqslant5000\)，所以会\(MLE\)，将\(j\)压成\(0/1\)就行了
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5,INF=1061109567;
int n,m;
int dp[N][2][3],now;
char s[N],t[N];
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
getchar(); for(int i=1;i<=n;++i) scanf("%c",&s[i]);
getchar(); for(int i=1;i<=m;++i) scanf("%c",&t[i]);
if(m>n){ printf("-1\n"); continue; }
memset(dp,0x3f,sizeof(dp));
now=0,dp[0][0][0]=1,dp[0][0][1]=0;
for(int j=1;j<=n;++j){
now^=1;
dp[0][now][0]=j*2+1,dp[0][now][1]=0,dp[0][now][2]=j;
for(int i=1;i<=m;++i){
dp[i][now][0]=dp[i][now][1]=dp[i][now][2]=INF;
if(i<=j){
if(t[i]==s[j]){
dp[i][now][0]=dp[i-1][now^1][0]+1,dp[i][now][2]=dp[i-1][now^1][2]+1;
if(t[i-1]==s[j-1]) dp[i][now][1]=dp[i-1][now^1][1];
dp[i][now][1]=min(dp[i][now][1],dp[i-1][now^1][0]);
}
dp[i][now][0]=min(dp[i][now][0],dp[i][now^1][0]+2);
dp[i][now][2]=min(dp[i][now][2],min(dp[i][now^1][1]+1,dp[i][now^1][2]+1));
}
// cout<<i<<" "<<j<<" --- "<<dp[i][now][0]<<" "<<dp[i][now][1]<<" "<<dp[i][now][2]<<endl;
}
}
if(min({dp[m][now][0],dp[m][now][1],dp[m][now][2]})>=INF) printf("-1\n");
else printf("%d\n",min({dp[m][now][0],dp[m][now][1],dp[m][now][2]}));
}
return 0;
}
[CF150D] Mission Impassable
看到\(l\)的范围，\(1\leqslant l\leqslant 150\)，区间DP的\(O(n^3)\)可以上了
设\(dp[i][j]\)为操作完\(s[i,j]\)后的最大权值，那么\(dp[i][j]\)有两种选择：全部删完或只删一部分，记\(f[i][j]\)为将\(s[i,j]\)全部删完后的最大权值
\]
然后，解决\(f[i][j]\)，因为删的方式可以十分杂乱，也就是可以分成好几个区间删除并且删除其中几个后又可以将一些区间合并然后继续，所以，不能直接上区间dp
而对于所有的区间，最后一步一定是删掉一个长度为\(k\)的回文串，所以我们考虑设\(g[i][j][k]\)为\(s[i,j]\)最后一步删掉一个长度为\(k\)的回文串的最大代价（不算删掉这个长度为\(k\)的回文串的代价）
也可以算上，主要是如果算上了代码里要写很多个\(+val[k]\)，太麻烦了
如果\(s[i]\)与\(s[j]\)不一起删
\]
如果一起删，且分别为区间的两端
\]
那么
\]
然后答案就是\(dp[1][n]\)
#include<bits/stdc++.h>
using namespace std;
const int N=155,INF=1e9;
int n,a[N],g[N][N][N],f[N][N],dp[N][N],ans;
char c[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),a[i]=a[i]==-1?-INF:a[i];
getchar(); for(int i=1;i<=n;++i) scanf("%c",&c[i]);
memset(f,-0x3f3f3f3f,sizeof(f)),memset(g,-0x3f3f3f3f,sizeof(g));
for(int i=1;i<=n+1;++i) f[i][i-1]=0;
for(int len=1;len<=n;++len)
for(int l=1,r;l+len-1<=n;++l){
r=l+len-1,f[l][r]=-INF,g[l][r][0]=-INF,g[r][l][0]=-INF;
for(int k=1;k<=len;++k){
if(c[l]==c[r]){
if(k==1) g[l][r][k]=max(f[l+1][r],f[l][r-1]);
else if(k==2) g[l][r][k]=max(g[l][r][k],f[l+1][r-1]);
else g[l][r][k]=max(g[l][r][k],g[l+1][r-1][k-2]);
}
for(int p=l;p<r;++p) g[l][r][k]=max(g[l][r][k],max(g[l][p][k]+f[p+1][r],f[l][p]+g[p+1][r][k]));
f[l][r]=max(f[l][r],g[l][r][k]+a[k]);
}
}
for(int len=1;len<=n;++len)
for(int l=1,r;l+len-1<=n;++l){
r=l+len-1,dp[l][r]=max(0,f[l][r]);
for(int k=l;k<r;++k) dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]);
}
printf("%d",max(dp[1][n],0));
return 0;
}
[SNOI2019]字符串
比较简单啊，找规律
考虑字符串\(aabcd\)
比较删除第一个\(a\)与删除\(b\)的字符串的大小：
a\(abcd\)
\(aa\)b\(cd\)
可与发现，若删除字符\(s[i]\)与字符\(s[j]\ \ (i<j)\)，需要比较的区间就是\(s[i+1,j-1]\)，并且，若删去相邻且相同的字符，得到的字符串的字典序相同
所以，可以将原字符\(S\)串变成一个新的字符串\(T\)，即将原字符串中相邻且相等的字符变成同一个字符，若\(S[i]\)与\(S[i+1]\)同属于一个\(T[k]\)，那么在排序中，\(i\)和\(i+1\)一定挨在一起，且\(i\)在\(i+1\)的前面
若\(S[i]\)与\(S[j]\)不同属一个\(T[j]\)，设\(S[i]\)属于\(T[bel[i]]\)，\(S[j]\)属于\(T[bel[j]]\)，就只需要比较\(T[bel[i]]\)与\(T[bel[i]+1]\)的大小，若大于，则\(i\)的排名小于\(j\)，否则大于\(j\)，于是就只需要比较每个\(T[i]\)与\(T[i+1]\)的大小，然后用一个类似后缀和什么的东西就可以\(O(n)\)解决了
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,tot,s[N],ans[N],now,head[N],nxt[N];
char a[N];
int main(){
scanf("%d",&n);
getchar();
for(int i=1,t;i<=n;++i){
scanf("%c",&t);
if(t!=a[tot]) a[++tot]=t,head[tot]=i;
else nxt[i-1]=i;
}
for(int i=1;i<tot;++i){
// cout<<i<<" "<<a[i]<<endl;
s[i]+=now;
if(a[i]-'a'<a[i+1]-'a') s[i]+=tot-i;
else ++now;
ans[s[i]]=i;
}
ans[now]=tot;
for(int i=0;i<tot;++i) for(int j=head[ans[i]];j;j=nxt[j]) printf("%d ",j);
return 0;
}
[CF1422E] Minlexes
对于题目进行一个解释：
\(abba\ \ \rightarrow \ \ aa\ \ \nrightarrow\) aa
设\(f[i]\)为删掉\(s[i,n]\)的最小字符串
若\(s[i]\not= s[i+1]\)，则\(f[i]=s[i]+f[i+1]\)
否则，可以选择\(s[i]\)与\(s[i+1]\)一起删
当\(s[i]>f[i+2][0]\)时，删掉
当\(s[i]<f[i+2][0]\)时，不删，\(f[i]=s[i]+s[i]+f[i+2]\)
若\(s[i]==f[i+2][0]\)，设\(f[i+2]\)的第一个与\(f[i+2][0]\)不相等的字符为\(dif\)
若\(dif>f[i+2][0]\)，删
否则，不删
然后就是\(f\)可能会\(MLE\)，我的方法比较笨，就是当\(f[i].size()>10\)时，将它直接变成题目要求的样子，所以我们需要一个单独的数组来记录每个\(f[i]\)的真实长度，再用一个\(dif\)数组记录\(f[i]\)的第一个与\(f[i][0]\)不相等的字符，就可以了
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int len,coiled[N],lenn[N];
char dif[N];
string s,f[N];
string str(char a){
string ans; ans=a;
return ans;
}
void delet(string &s,int pos){
string s1(begin(s),begin(s)+5),s2(end(s)-2,end(s));
s=s1+s2;
}
int main(){
cin>>s;
len=s.size();
f[len-1]+=s[len-1],lenn[len-1]=1,dif[len-1]='?';
for(int i=len-2;i>-1;--i){
if(s[i]!=s[i+1]){
f[i]=s[i]+f[i+1],lenn[i]=lenn[i+1]+1;
if(s[i]!=f[i+1][0]) dif[i]=f[i+1][0];
else dif[i]=dif[i+1];
}else{
if(!lenn[i+2]){ dif[i]='?'; continue; }
if(s[i]!=f[i+2][0]){
if(s[i]>f[i+2][0]) f[i]=f[i+2],lenn[i]=lenn[i+2],dif[i]=dif[i+2];
else f[i]=str(s[i])+str(s[i])+f[i+2],lenn[i]=lenn[i+2]+2,dif[i]=f[i+2][0];
}else{
if(dif[i+2]>f[i+2][0]) f[i]=str(s[i])+str(s[i])+f[i+2],lenn[i]=lenn[i+2]+2;
else f[i]=f[i+2],lenn[i]=lenn[i+2];
dif[i]=dif[i+2];
}
}
if(f[i].size()>10) delet(f[i],i);
}
for(int i=0;i<len;++i){
printf("%d ",lenn[i]);
if(lenn[i]<=10) cout<<f[i]<<endl;
else{
for(int j=0;j<5;++j) printf("%c",f[i][j]);
printf("...");
for(int j=f[i].size()-2;j<f[i].size();++j) printf("%c",f[i][j]);
printf("\n");
}
}
return 0;
}
[CF1562E] Rescue Niwen!
自己简单搞个字符串模一模，就可以发现排好序后的序列呈一个分成\(n\)段，第\(i\)段中的所有字串的开头都是\(s[i]\)，且整个段内为上升序列
一个段内的形式大概如下：\(a\) \(ab\) \(abc\) \(abcd\)
也就是说，若选了该段中的第\(i\)个串，则从\(i\)到段末的串都可以选择
这启示我们，若答案的最长序列中以第\(i\)段中的子串结尾，则答案末尾的这个子串一定是第\(i\)段的末尾的子串
还有，若可以由第\(j\)段中的第\(k\)个子串到达第\(i\)段的第\(l\)个子串，那么第\(j\)段的\(k\)个到最后一个子串都可以到达第\(i\)段中的第\(l\)个字串
因为第\(j\)段中的第\(k\)个子串已经小于第i段的第\(l\)个子串了，所以无论在第\(k\)个子串后面加多少个字符，都会小于第\(l\)个子串
所以，上dp
\(dp[i]\)表示以第\(i\)段的最后一个字串为序列的结尾的最长序列，\(lcp[i][j]\)表示\(s[i,n]\)与\(s[j,n]\)的\(lcp\)
\]
\]
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
int n,dp[N],ans,lcp[N][N];
char s[N];
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
getchar(); scanf("%s",s+1);
for(int i=n;i;--i) for(int j=n;j;--j) lcp[i][n+1]=lcp[n+1][i]=0,lcp[i][j]=((s[i]==s[j])?lcp[i+1][j+1]+1:0);
ans=0;
for(int i=1;i<=n;++i){
dp[i]=n-i+1;
for(int j=1;j<i;++j) if(lcp[i][j]<n-i+1&&s[i+lcp[i][j]]>s[j+lcp[i][j]]) dp[i]=max(dp[i],dp[j]+n-i+1-lcp[i][j]);
ans=max(ans,dp[i]);
}
printf("%d\n",ans);
}
return 0;
}
