4 条题解

  • 0
    @ 2025-4-23 9:47:50

    首先看到这个题，不难想到是区间dp。但是如果按照http://oi.sdshiyan.cn/p/169 这道题来写只能得到40分。因为@、￥的匹配是不能嵌套的。

    我们使用dp[l][r][0]表示[l,r]这段区间不放@但可能有￥的最好长度；dp[l][r][1]表示[l,r]这段区间中间有@来匹配后面的￥的最好长度。

    显然dp[i][i][1]=dp[i][i][0]=1;（i from 1 to n）。

    转移时：

    for(int i=l; i<r; ++i) {
	dp[l][r][0]=min(dp[l][r][0],dp[l][i][0]+r-i);
	dp[l][r][1]=min(dp[l][r][1],min(dp[l][i][0],dp[l][i][1])+1+min(dp[i+1][r][0],dp[i+1][r][1]));
}

    第一行是因为前面有了一段有$的了，后面不能再有了，所以是+r-i。

    第二行是枚举中间@的位置，这样前后方什么都可以了。

    然后

    if(!(len&1)&&getha(l,l+r>>1)==getha((l+r>>1)+1,r)) {
	dp[l][r][0]=min(dp[l][r][0],dp[l][l+r>>1][0]+1);
}

    就是如果能分成两段一样的，就用$表示，这样$匹配的是开头默认的@，中间还是没有@，所以转移到dp[l][r][0]这里。

    代码非常的短。

    #include<bits/stdc++.h>
#define int long long
#define uint unsigned long long
using namespace std;
int n;
string s;
uint fac[55],ha[55];
inline uint getha(int l,int r){  return ha[r]-ha[l-1]*fac[r-l+1];  }
int dp[55][55][2];
signed main() {
    std::ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>s;
	n=s.size(),s=" "+s;
	fac[0]=1;for(int i=1;i<=n;++i)fac[i]=fac[i-1]*13331,ha[i]=ha[i-1]*13331+s[i],dp[i][i][1]=dp[i][i][0]=1;
	for(int len=2;len<=n;++len){
		for(int l=1;l+len-1<=n;++l){
			int r=l+len-1;
			dp[l][r][1]=dp[l][r][0]=len;
			for(int i=l;i<r;++i)dp[l][r][0]=min(dp[l][r][0],dp[l][i][0]+r-i),dp[l][r][1]=min(dp[l][r][1],min(dp[l][i][0],dp[l][i][1])+1+min(dp[i+1][r][0],dp[i+1][r][1]));
			if(!(len&1)&&getha(l,l+r>>1)==getha((l+r>>1)+1,r)) dp[l][r][0]=min(dp[l][r][0],dp[l][l+r>>1][0]+1);
		}
	} 
	cout<<min(dp[1][n][0],dp[1][n][1]);
	return 0;
}
    • 0
      @ 2025-4-23 9:47:40

      虽然说题解比较长，但是比其他题解详细，请耐心阅读

      这个题跟这个题很像啊，考虑区间Dp。

      但是我们注意到本题与该题的区别是这个题无法嵌套，因为这道题的一个 $ 是将该位置与前面最近的一个 @ 相匹配然后复制的。

      因为在 i=1i=1 的位置上是不能出现 @ 的，所以我们对于每一个位置 ii 都先假设 压缩后的字符串中 i−1i-1 的位置出现了 @ ，这暂且称作没有真正的出现，这个 @ 是仅仅假设出来的，并不算进答案里。

      • 剖析一下为什么可以这样假设
      • 1.首先我们注意到第 11 个位置如果能压缩的话，第 00 个位置上应该有一个 @ 的
      • 2.对于一个区间的字串 [i,j][i,j] 如果需要被压缩，那么我们设的这个虚假的 @ ，一定也会被后面转移到
      • 3.如果字串 [i,j][i,j] 不需要被压缩，那么也不会算进答案中

      即设 dpi,j,0/1dp_{i,j,0/1} 表示在区间 [i,j][i,j] 中有没有真正的出现 @，下面开始转移

      首先考虑压能压缩情况：即对于一个字串 [l,r][l,r] 中，S[l,mid]=S[mid+1,r]S_{[l,mid]}=S_{[mid+1,r]} ，那么我们有转移:

      dpi,j,0=min⁡{dpi,mid,0+1}dp_{i,j,0}=\min \{ dp_{i,mid,0}+1 \}

      这就是将两个相同的字串压缩的操作，因为我们已经有一个虚假的 @ 了，仅需将被压缩的字串的最小串复制一遍后再加上一个 $ 即可

      检查两个字串是否相同我们可以使用哈希或者直接暴力也可以

      接下来考虑将两段字串拼在一块，则有：

      dpi,j,0=min⁡k=ij{dpi,k,0+j−k}dp_{i,j,0}=\min_{k=i}^{j} \{ dp_{i,k,0} +j-k \} $$dp_{i,j,1}=\min_{k=i}^{j} \{ \min\{ dp_{i,k,0},dp_{i,k,1}\} + \min\{ dp_{k+1,j,0},dp{k+1,j,1}\} +1 \} $$

      对于第一个式子来解析：首先对于拼在一起的两个字串，因为 i−1i-1 的位置我们虚构了一个 @ 所以说我们的字串 [i,k][i,k] 还是可以压缩的，但是后面的部分就不可压缩了，因为要保证 [l,r][l,r] 里没有 @ ，即加上原本的长度 j−kj-k

      对于第二个式子则是取前一部分压缩后的与后一部分压缩后的长度相加并且加上后一部分压缩所使用的 @

      代码也很简洁（我觉得其他人写的都史）

      #include<iostream>
#include<cstring>
#include<cstdio>
#define N 55
#define P 13331
#define unint unsigned long long
using namespace std;
bool Test_MLE_start;
int T=1,n;
char s[N];
int fac[N],h[N];
int dp[N][N][2];
inline int reads(){
	char c=getchar();
	int sum=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		sum=(sum<<3)+(sum<<1)+(c^'0');
		c=getchar();
	}
	return sum*f;
}
inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
bool check(int l1,int r1,int l2,int r2){
	int hh1=(h[r1]-h[l1-1])*fac[l2-l1],hh2=h[r2]-h[l2-1];
	return hh1==hh2;
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	T=reads();
	while(T--){
		clr();
		memset(dp,0x3f,sizeof(dp));
		scanf("%s",s+1);
		n=strlen(s+1);
		fac[0]=1;
		for(int i=1;i<=n;i++){
			fac[i]=fac[i-1]*P;
			h[i]=h[i-1]+s[i]*fac[i];
			dp[i][i][0]=1,dp[i][i][1]=2;
		}
		for(int len=2;len<=n;len++){
			for(int i=1,j=i+len-1;j<=n;i++,j++){
				int mid=(i+j)>>1;
				if(check(i,mid,mid+1,j)) dp[i][j][0]=min(dp[i][j][0],dp[i][mid][0]+1);
				for(int k=i;k<=j;k++){
					dp[i][j][0]=min(dp[i][j][0],dp[i][k][0]+j-k);
					dp[i][j][1]=min(dp[i][j][1],min(dp[i][k][0],dp[i][k][1])+min(dp[k+1][j][0],dp[k+1][j][1])+1);
				}
			}
		}
		printf("%d\n",min(dp[1][n][0],dp[1][n][1]));
	}
	return 0;
}
      • -1
        @ 2025-4-23 10:49:28

        最好表示 题解

        受到2025-04-18比赛中C最好表示的启发，不难想到使用区间dp解决。

        (当然没有做过类似的题也比较容易想到，因为第一本题数据范围很小，dp可以轻松开多维；第二暴力很难打，可能出现的状态实在是太多了。

        一些问题

        1.dp到底开几维？

        一开始想的是很基础的dp[i][j]表示从i~j的最好表示长度，最后输出即为dp[1][n]。然后发现自己死也写不出来...

        why？找不到前一个标记@，如果想使用＄不知道该复制哪一段，因为这种压缩可能存在嵌套的关系，比如abca bc bc bcbc----->abca@bc＄＄

        第二个＄表示的是前面的bc＄，即bcbc。

        这个嵌套关系还会导致一个问题，就是如果我们找到一段循环节，并不能简单的在这段循环节前后加上@和＄，这是我们思考的误区和审题的不当。

        举个栗子，假如一个字符串xyyxyy，我们第一步把它压缩成(@)xyy＄，然后我们又想把循环节里面的yy压缩成@y＄（暂且不考虑这样变换后是否更优），那么原字符串就被压缩成了(@)x@y＄＄。

        看似没毛病，实则不然。题目要求“上一个 @ 的位置之后至当前 $ 的位置之前的字符串”，即这个＄前最近的@，那么按照这个要求把这个压缩的字符串展开，会得到xyy yy，显然不符。

        所以问题在哪？问题主要出在我们为了压缩内层的yy而打的标记@上，它挡住了结尾＄去找开头不存在的（@）的路。如果内层被打过标记@，外层就不能按照原来的方式压缩了，所以可以给dp多加一维0/1，表示i~j之间是否存在标记@ 。相应地，答案输出也将变为min(dp[1][n][0],dp[1][n][1])。

        2.分几种情况进行压缩的状态转移？

        首先枚举长度len，枚举起点i，以计算终点j是常规的区间dp操作了。如果i~j这一段里没有标记，我们就可以放心大胆的去找是不是有循环节，那么i~j这一段的长度就可以缩短到原来的一半再+1。这和开头提到的那道C题几乎是一摸一样的处理方案。

        如果不存在这样可被压缩的循环节，那么就区间dp老套路枚举断点k。接下来继续分内部有无@标记两种情况讨论：

        ①区间里没有标记：

        dp[i][j][0]=min(dp[i][j][0],dp[i][k][0]+j-k);

        ②区间里有标记：

        dp[i][j][1]=min(dp[i][j][1],min(dp[i][k][0],dp[i][k][1])+1+min(dp[k+1][j][0],dp[k+1][j][1]));

        注意k点左右两端都要取有无标记的min!!!

        Anything Else?

        给dp赋极大初值，不过记得处理dp[i][i][0]和dp[i][i][1]的情况。

        还有别把判断循环节的check()写错。

        CODE

        #include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=57;
int n,dp[N][N][3];
char s[N];
void init(){
	memset(dp,0x7f7f7f,sizeof dp);
	for(int i = 1;i<=n;i++){
		dp[i][i][0]=1;
		dp[i][i][1]=2;
	}
}
int check(int l,int r,int len){//l~r是否循环节 
	if((r-l+1)%len)return 0;
	for(int i = l;i<=l+len-1;i++)
		for(int j = i+len;j<=r;j+=len)
			if(s[i]!=s[j])return 0;
	return 1;
}
signed main(){
	//freopen("best.txt","r",stdin);
	scanf("%s",s+1);
	n=strlen(s+1);
	init();
	for(int len = 2;len<=n;len++){
		for(int i = 1;i<=n;i++){
			int j=i+len-1;
			if(j>n)break;
			if(check(i,j,(j-i+1)>>1)){
				int mid=(i+j)>>1;
				dp[i][j][0]=min(dp[i][j][0],dp[i][mid][0]+1);
			}
			for(int k = i;k<=j;k++){
				dp[i][j][0]=min(dp[i][j][0],dp[i][k][0]+j-k);
				dp[i][j][1]=min(dp[i][j][1],min(dp[i][k][0],dp[i][k][1])+1+min(dp[k+1][j][0],dp[k+1][j][1]));
			}
		}
	}
	cout<<min(dp[1][n][0],dp[1][n][1])<<'\n';
	return 0;
}
        • -3
          @ 2025-4-23 9:33:13

          首先看到这个题，不难想到是区间dp，然后我们定义f[l][r]为l到r的最好表示，我们发现这样表示不出加入@ 的情况，于是我们再定义一维，变为f[l][r][k]，k=0时表示有且仅有一个@，且这个@位于l的前一个位置，k=1时表示l到r无论有几个@的最好表示

          那么我们可以想到转移方法，一种是 枚举断点直接合并，一种是判断中点前后是否一样，如果一样就尝试缩短

          初始对于任意i属于1-n,f[i][i][1]=1 f[i][i][0] = 1 + (i != 1)

          然后目标是f[1][n][1]

          转移过程扔代码里了

          code :

          #include <bits/stdc++.h>
using namespace std;

bool mlest;

double tlest, tleed;

inline int R() {
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(isdigit(ch)) {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}

inline void W(int x) {
	if(x < 0) {
		x = -x;
		putchar('-');
	}
	if(x > 9) W(x/10);
	putchar(x%10+'0');
}

const int N = 60;

const int B = 13331;

string s;

int n;

int f[N][N][2];

unsigned long long h[N], p[N];

void read() {
	cin >> s;
	n = s.size();
	s = " " + s;
}

unsigned long long get(int l,int r) {
	return h[r] - h[l-1] * p[r-l+1];
}

void init() {
	p[0] = 1;
	for(int i = 1; i <= n; i++) {
		h[i] = h[i-1] * B + s[i];
		p[i] = p[i-1] * B;
	}
}

void compute() {
	for(int i = 1; i <= n; i++) {
		f[i][i][1] = 1;
		f[i][i][0] = 1 + (int)(i != 1);
	}
	for(int len = 2; len <= n; len++) {
		for(int l = 1; l + len - 1 <= n; l++) {
			int r = l + len - 1;
			f[l][r][0] = INT_MAX;
			f[l][r][1] = INT_MAX;
			for(int m = l; m < r; m++) {
				f[l][r][0] = min(f[l][r][0],f[l][m][0]+r-m);
				f[l][r][1] = min(f[l][r][1],f[l][m][1]+f[m+1][r][1]);
			}
			int mid = (l + r) >> 1;
			if(len % 2 || get(l,mid) != get(mid+1,r)) continue;
			if(l == 1) f[l][r][0] = min(f[l][r][0],min(f[l][mid][0]+1,mid-l+2));
			else f[l][r][0] = min(f[l][r][0],min(f[l][mid][0]+1,mid-l+3));
			f[l][r][1] = min(f[l][r][1],f[l][r][0]);
		}
	}
	W(f[1][n][1]);
}

void clear() {

}

void run() {
	read();
	init();
	compute();
	clear();
}

bool mleed;

void wa() {
	cout << "\n" << tleed-tlest << "ms\n" << (&mleed-&mlest-1)/1024.0/1024.0 << "MB\n";
}

void fre(string s) {
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

int main() {
//	fre("");
	tlest = clock();
	run();
	tleed = clock();
//	wa();
	return 0;
}
          • @ 2025-4-23 9:40:04

            dedededededededededede

          • @ 2025-4-23 9:45:53

            dédèdèdēdědēdèdēdědědé

        • 1

        最好表示

        信息

        ID
        174
        时间
        1000ms
        内存
        256MiB
        难度
        9
        标签
        (无)
        递交数
        91
        已通过
        10
        上传者
        1. 关于
        2. 联系我们
        3. 隐私
        4. 服务条款
        5. 版权申诉
        6. Language
        7. 兼容模式
        8. 主题
        3. Worker 0, 55ms
        4. Powered by Hydro v4.18.3 Community