[SCOI2007]压缩（区间dp）

神仙题，看了半天题解才看明白。。。

因为题目里说如果没有m，会自动默认m在最前面。

我们设计状态为dp[l][r][0/1]为在区间l到r中有没有m的最小长度。

转移：枚举我们要压缩的起点，dp[l][i][1]+dp[i+1][r][1]+1，加一是指我们要压缩后半段，在断点处加上一个m。

如果我们不压缩后半段，那转移就为dp[l][i][1]+r-i，因为后面不动，就直接加上。

如果发现它可以压缩，直接dp[l][mid][0]+1，注意tag为0。

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 55

using namespace std;

int dp[N][N][],n;

char s[N];

inline bool pd(int l,int r){

    if((r-l+)%==)return ;

    int len=(r-l+)/;

    for(int i=l;i<=l+len-;++i)

      if(s[i]!=s[i+len])return ;

     return ;

}

int dfs(int l,int r,int tag){

    if(dp[l][r][tag])return dp[l][r][tag];

    int ans=r-l+;

    if(ans==)return ans;

    if(tag)

      for(int i=l;i<r;++i)ans=min(ans,dfs(l,i,)++dfs(i+,r,));

    for(int i=l;i<r;++i)ans=min(ans,dfs(l,i,tag)+r-i);

    if(pd(l,r))ans=min(ans,dfs(l,(l+r)>>,)+);

    return dp[l][r][tag]=ans;

}

int main(){

    scanf("%s",s);

    n=strlen(s);

    printf("%d",dfs(,n-,));

    return ;

}

巴特西

[SCOI2007]压缩（区间dp）

最新文章

热门文章