3790: 神奇项链

本文主要是介绍3790: 神奇项链，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

容易发现，处理回文串的时候得到的答案是可以去更新答案的，
即 令 $f[i]$ 表示处理前 $i$ 个最小由几个回文串构成，
那么，对于第$i$个位置，他由 $[i-p[i],n]$能更新的就是 前 $[1,i+p[i]-1]$，
因为前后缀相同能直接放在一起，容易正确性很显然
然后dp方程用树状数组维护即可。
c++代码如下：

#include<bits/stdc++.h>
#define lowbit(x) (x & -x)
#define rep(i,x,y) for(register int i = x; i <= y; ++ i)
#define repd(i,x,y) for(register int i = x; i >= y; -- i)
using namespace std;
typedef long long ll;
template<typename T>inline void read(T&x)
{char c;int sign = 1;x = 0;do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));x *= sign;
}const int N = 2e5+50;
char s[N];
int n,p[N],mx;
int t[N];inline void update(int x,int w)
{if(x <= 0) x = 1;for(register int i = x;i <= n; i += lowbit(i))t[i] = min(t[i],w); 
}inline int query(int x)
{int ans = 0x3f3f3f3f;for(register int i = x; i ; i -= lowbit(i))ans = min(ans,t[i]);return ans;
}int main()
{while(~scanf("%s",s + 1)){memset(t,0x3f,sizeof t);n = strlen(s + 1);repd(i,n,1) s[i<<1] = s[i],s[i<<1|1] = '#';s[0] = '?'; s[1] = '#';mx = 0; n <<= 1;++n;t[n+1] = t[n+2] = t[n+3] = 0;rep(i,1,n){if(p[mx] + mx > i) p[i] = min(p[mx] + mx - i,p[mx*2-i] );else p[i] = 1;while(s[i - p[i]] == s[i + p[i]]) ++ p[i];if(p[i] + i > mx + p[mx]) mx = i;int x = query(n - i + 1 + p[i]);update(n - i + 1 - p[i] + 1,x + 1);}printf("%d\n",query(2)-1);}return 0;
}

这篇关于3790: 神奇项链的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---