网站建设中目录,如何开无货源网店,建设企业网站流程,爱演示网看了正解。我觉得很厉害。虽然用减枝水过去了。
区间 d p dp dp。但是这个转移怎么看都不是 O ( 1 ) O(1) O(1)的。 border \text{border} border 那么 trick \text{trick} trick应该都能看出来。能进行剪切操作当且仅当 s [ l , p ] s [ q , r ] s_{[l,p]}s_{[q,r]} s[l,p]…看了正解。我觉得很厉害。虽然用减枝水过去了。
区间 d p dp dp。但是这个转移怎么看都不是 O ( 1 ) O(1) O(1)的。 border \text{border} border 那么 trick \text{trick} trick应该都能看出来。能进行剪切操作当且仅当 s [ l , p ] s [ q , r ] s_{[l,p]}s_{[q,r]} s[l,p]s[q,r]显然直接跳 fail \text{fail} fail链即可。厉害的地方来了对于两个相同的子串只用计算一次而每跳一次至少会出现一对相同的子串因此总转移数目只有 O ( n 2 ) O(n^2) O(n2)。
问题在于求出区间 [ l , r ] [l,r] [l,r]内最多能选多少个不重复的 s [ l , p ] s_{[l,p]} s[l,p]。更厉害的地方来了这个东西可以倍增预处理设 g l , r , k g_{l,r,k} gl,r,k表示和 s [ l , r ] s_{[l,r]} s[l,r]相同的不重叠的第 2 k 2^k 2k个串的左端点然后就做完了。
复杂度是严格的 O ( n 2 log n ) O(n^2\log n) O(n2logn)。 当然减一减枝也能过。
#includebits/stdc.h
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
int n,nxt[2505][2505],to[2505][2505];
int trie[2505*2505][26],g[2505][2505][12],len[2505*2505],tot;
ll dp[2505][2505],A,B,C;
vectorintpos[2505*2505];
string s;
void chmin(ll x,ll y){xmin(x,y);}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinns;memset(dp,0x3f,sizeof dp);cinABC;//fixedfor(int i0;in;i){nxt[i][i]i-1;for(int ji1;jn;j){int knxt[i][j-1];while(kis[k1]!s[j])knxt[i][k];if(s[k1]s[j])k;nxt[i][j]k;}}for(int i0;in;i){int it0;for(int ji;jn;j){if(!trie[it][s[j]-a])trie[it][s[j]-a]tot,len[tot]j-i1;ittrie[it][s[j]-a];pos[it].pb(i);to[i][j]it;}}for(int i1;itot;i){sort(pos[i].begin(),pos[i].end());int k0;for(int j0;jpos[i].size();j){while(kpos[i].size()pos[i][k]-pos[i][j]len[i])k;if(k!pos[i].size()){g[pos[i][j]][len[i]][0]pos[i][k];}}}for(int k1;k11;k){for(int i0;in;i){for(int j1;jn-i;j){if(g[i][j][k-1])g[i][j][k]g[g[i][j][k-1]][j][k-1];}}}for(int i0;in;i)dp[i][i]A;for(int len2;lenn;len){for(int i0;in-len1;i){int jilen-1;if(pos[to[i][j]][0]!i){dp[i][j]dp[pos[to[i][j]][0]][pos[to[i][j]][0]len-1];continue;}chmin(dp[i][j],dp[i1][j]A);chmin(dp[i][j],dp[i][j-1]A);//fixedfor(int knxt[i][j];ki;knxt[i][k]){int tot1,nowli,len2k-i1;for(int l11;l0;l--){if(g[nowl][len2][l]g[nowl][len2][l]j-len21){tot1l;nowlg[nowl][len2][l];}}chmin(dp[i][j],dp[i][k]Btot*C(len-tot*len2)*A);}}}coutdp[0][n-1];
}
