題目鏈接：點擊查看
題目大意：給出一個只由數字 1 ~ 9 組成的字符串 s，首先規定 f( l , r ) 為字符串 s 的區間 [ l , r ] 中的數位和，再規定 x-prime 需要同時滿足以下條件：
f( l1 , r1 ) = x不存在 ( l2 , r2 )，使得： l1 <= l2 <= r2 <= r1f( l2 , r2?) != xx 可以被 f( l2 , r2 )?整除
問最少刪掉字符串 s 中的多少個字母，可以使得整個字符串中不含有 x-prime
題目分析：首先對 x ∈ [ 1 , 20 ] 都打個表，發現當 x = 19 時，有最多的 x-prime ，為 2399 個，這樣對于每個 x 就可以將需要刪除的匹配串暴力dfs出來，這樣問題就變得和之前一道題目很像了：https://blog.csdn.net/qq_45458915/article/details/104243061
只不過那道題目是對相應的位置修改為別的字母，這個題目是直接將相應位置刪除了，在 dp 轉移的過程中有點小的區別，其他的幾乎都一模一樣了
dp[ i ][ j ] 代表到了字符串 s 的第 i 個位置，狀態為 j 時的最小刪除數，轉移的話，因為是可以刪除，所以 dp[ i + 1 ][ j ] = dp[ i ][ j ] + 1 這個代表需要將第 i + 1 位刪除，而當 trie[ j ][ s[ i?] ] 不是 x-prime 時，可以不用刪除，也就是 dp[ i + 1 ][ trie[ j ][ s[ i ] ]?] = dp[ i ][ j ]
代碼：
?
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e3+100;const int M=5e3+100;int trie[M][10],fail[M],cnt;bool vis[M];char s[M],str[N];int dp[N][M],x;void insert_word()
{int len=strlen(s);int pos=0;for(int i=0;i<len;i++){int to=s[i]-'0';if(!trie[pos][to])trie[pos][to]=++cnt;pos=trie[pos][to];}vis[pos]=true;
}void getfail()
{queue<int>q;for(int i=0;i<10;i++){if(trie[0][i]){fail[trie[0][i]]=0;q.push(trie[0][i]);}}while(!q.empty()){int cur=q.front();q.pop();vis[cur]|=vis[fail[cur]];for(int i=0;i<10;i++){if(trie[cur][i]){fail[trie[cur][i]]=trie[fail[cur]][i];q.push(trie[cur][i]);}elsetrie[cur][i]=trie[fail[cur]][i];}}
}void dfs(int sum,int step)
{if(sum>x)return;if(sum==x){s[step]=0;for(int i=0;i<step;i++){int d=0;for(int j=i;j<step;j++){d+=s[j]-'0';if(x%d==0&&x!=d)goto end;}}insert_word();end:;return;}for(int i=1;i<=9;i++){s[step]=i+'0';dfs(sum+i,step+1);}
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);scanf("%s%d",str,&x);dfs(0,0);getfail();int n=strlen(str);memset(dp,inf,sizeof(dp));dp[0][0]=0;for(int i=0;i<n;i++)for(int j=0;j<=cnt;j++)if(dp[i][j]<inf){dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1);//得刪 int nj=trie[j][str[i]-'0'];if(!vis[nj])//不用刪 dp[i+1][nj]=min(dp[i+1][nj],dp[i][j]);}int ans=inf;for(int i=0;i<=cnt;i++)ans=min(ans,dp[n][i]);printf("%d\n",ans);return 0;
}
?
超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生
總結
以上是生活随笔為你收集整理的CodeForces - 1400F x-prime Substrings(AC自动机+dp)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
