做风险代理案源的网站,开发一款app的公司,一般做网站是用什么语言开发的,wordpress 窗口传送门 dalao们怎么状态都设的两维以上啊?qwq 完全可以一维状态的说 设\(f[i]\)为前缀i的答案,转移就枚举从前面哪里转移过来\(f[i]min(f[j-1]w(j,i))(j\in [1,i])\) 现在要知道\(w(i,j)\)怎么写,也就是区间\([i,j]\)的最小长度(要求区间最多只能在开头有一个W),首先不压缩的长…传送门 dalao们怎么状态都设的两维以上啊?qwq 完全可以一维状态的说 设\(f[i]\)为前缀i的答案,转移就枚举从前面哪里转移过来\(f[i]min(f[j-1]w(j,i))(j\in [1,i])\) 现在要知道\(w(i,j)\)怎么写,也就是区间\([i,j]\)的最小长度(要求区间最多只能在开头有一个W),首先不压缩的长度就是原长度,然后压缩的话先要在开头加W,然后每次压缩一个最长的可以拆成两个相同串的前缀,压缩完后长度会加上1(后面接R),减去那个前缀的一半长度,然后那个前缀会缩掉后一半.把这些所有的长度取min就是这个区间的答案.这个压缩过程可以结合样例理解 注意开头是默认加好了W的 细节详见代码 #includebits/stdc.h
#define LL long long
#define il inline
#define re register
#define uLL unsigned long longusing namespace std;
const int N55;
il int rd()
{int x0,w1;char ch0;while(ch0||ch9) {if(ch-) w-1;chgetchar();}while(ch0ch9) {x(x3)(x1)(ch^48);chgetchar();}return x*w;
}
char cc[N];
uLL ha[N],bs[N];
il uLL hh(int l,int r){return ha[r]-ha[l-1]*bs[r-l1];}
int n,f[N];
il int w(int l,int r)
{int anr-l1(l1),nw1; //左端点为1,由于开头加好了W,所以这里不压缩长度先加上1平衡压缩要加上的Wwhile(lr){int mid(lr)1;while(lrhh(l,mid)!hh(mid1,r)) --r,nw,mid(lr)1;if(lr) break;nw,rmid;anmin(an,nwr-l1); //代价也可以看做M的个数R的个数后面的一些零碎字母前半截前缀长度}return an;
}int main()
{scanf(%s,cc1),nstrlen(cc1);bs[0]1;for(int i1;in;i) bs[i]bs[i-1]*233,ha[i]ha[i-1]*233cc[i],f[i]i1;for(int i1;in;i)for(int j1;ji;j)f[i]min(f[i],f[j-1]w(j,i));printf(%d\n,f[n]-1); //把开头没有的W减掉
}转载于:https://www.cnblogs.com/smyjr/p/10353647.html
