NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...
BX正在進行一個字串游戲,他手上有一個字串L,以及其他一些字串的集合S,然後他可以進行以下操作:對於一個在集合S中的字串p,如果p在L中出現,BX就可以選擇是否將其刪除,如果刪除,則將刪除後L分裂成的左右兩部分合並。舉個例子,L=’abcdefg’ , S={‘de’},如果BX選擇將’de’從L中刪去,則刪後的L=’abcfg’。現在BX可以進行任意多次操作(刪的次數,順序都隨意),他想知道最後L串的最短長度是多少。

f[i][j][k][p]表示i到j是否可以表示第k個字串的前p個字元。
c[i][j]表示i到j是否可以全部刪去。
有兩種轉移‘
f[j-1][k][p-1]&&st[k][p]==S[j]
f[d][k][p]&&c[d 1][j]
類似區間dp的東西可以採用固定一端,列舉另一端的方法

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>

#define ll long long
#define inf 1e9
#define eps 1e-10
#define md
#define N
using namespace std;
bool f[170][35][25],c[170][170];
int dp[170],len[35];
char S[170],st[35][25];
int main()
{
scanf(“%s”,S 1); int lth=strlen(S 1);
int n;
scanf(“%d”,&n);
for (int i=1;i<=n;i )
{
scanf(“%s”,st[i] 1);
len[i]=strlen(st[i] 1);
}
for (int i=lth;i;i–)
{
memset(f,0,sizeof(f));
for (int k=1;k<=n;k )
f[i-1][k][0]=1;
for (int j=i;j<=lth;j )
{
for (int k=1;k<=n;k )
for (int p=1;p<=len[k];p )
f[j][k][p]|=(f[j-1][k][p-1]&&st[k][p]==S[j]);
for (int d=i;d<=j;d )
if (c[d 1][j])
{
for (int k=1;k<=n;k )
for (int p=1;p<=len[k];p )
f[j][k][p]|=f[d][k][p];
}
}
for (int j=i;j<=lth;j )
for (int k=1;k<=n;k )
c[i][j]|=f[j][k][len[k]];
}
for (int i=1;i<=lth;i )
{
dp[i]=dp[i-1] 1;
for (int j=1;j<=i;j )
if (c[j][i]) dp[i]=min(dp[i],dp[j-1]);
}
printf(“%d\n”,dp[lth]);
return 0;
}

相關文章

程式語言 最新文章