网站建设用什么代码,网页制作网站花店,电商网站建设与课程设计,网站产品简介题意#xff1a;给出一个由大写字母组成的长度为n的串#xff0c;然后尽量折叠成一个尽量短的串#xff0c;折叠可以嵌套。 思路#xff1a;区间dp#xff0c;dp#xff08;i#xff0c;j#xff09;表示区间#xff08;i#xff0c;j#xff09;的最短的串的长度给出一个由大写字母组成的长度为n的串然后尽量折叠成一个尽量短的串折叠可以嵌套。 思路区间dpdpij表示区间ij的最短的串的长度asij表示i到j的答案有两个状态要处理1.该串本身是重复串缩段到最短。2.该串不是重复然后枚举他的分割点把两段最短找出来然后合并。
code #include bits/stdc.h
using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;const int INF0x3fffffff;
const int inf-INF;
const int N1000000;
const int M105;
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 frt(i,s,t) for (int is;it;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);int dp[M][M];
string s;
string as[M][M];
int check(int l,int r){ft(i,1,(r-l1)/2){if ((r-l1)%i) continue;bool f1;ft(j,l,r-i)if (s[j]!s[ji]){f0;break;}if (f) return i;}return 0;
}
int sol(int l,int r){int ansdp[l][r];if (ans!-1) return ans;if (lr){as[l][r]s[l];return ans1;}int retINF,k;ft(i,l,r-1){int tpsol(l,i)sol(i1,r);if (tpret) ki,rettp;}as[l][r]as[l][k]as[k1][r];retsol(l,k)sol(k1,r);int tcheck(l,r);if (t){bool f1;ft(i,l,r)if (s[i](||s[i])) f0;char ts[10];sprintf(ts,%d,(r-l1)/t);string ttts;tt(as[l][lt-1]);if (ftt.size()ret){rettt.size();as[l][r]tt;}}return ansret;
}
int main()
{while(cins){cls(dp,-1);int lens.size()-1;sol(0,len);coutas[0][len]endl;}
}