2018-07-26 23:33:41

A[1]=4

F[i][j]表示在前i个字符中，分成j段，所含有的最多单词数 根据做题经验——《乘积最大》和一部分的思考可以得出

F[i][j]=max{F[x][j-1]+(t∈[x+1,i]，A[t]<=i的个数)}

this/isabookyouareaoh

LuckyCloud
#include<cstdio>
#include<cstring>
using namespace std;
{
int cnt=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){cnt=cnt*10+ch-48;ch=getchar();}
return cnt*f;
}
int len,dp[210][45],p,k,n,t,l[7],a[210],c[210][210];
char s[210],s1[20],word[7][200];
inline int max(int x,int y)
{
return x>y?x:y;
}
inline int min(int x,int y)
{
return x<y?x:y;
}
inline bool check(int x,int t)
{
for (int i=t;i<=t+l[x]-1;i++)
if (s[i]!=word[x][i-t+1]) return false;
return true;
}
inline int query(int num,int x)
{
int ret=0;
for (;x;x-=x&-x)
ret+=c[num][x];
return ret;
}
int main()
{
for (int i=1;i<=p;i++)
{
scanf("%s",s1+1);
len=strlen(s1+1);
for (int j=1;j<=len;j++)
s[++n]=s1[j];
}
for (int i=1;i<=t;i++)
{
scanf("%s",word[i]+1);
l[i]=strlen(word[i]+1);
}

memset(a,127/3,sizeof(a));
for (int i=1;i<=t;i++)
for (int x=1;x<=n-l[i]+1;x++)
if (check(i,x)) a[x]=min(a[x],x+l[i]-1);
memset(dp,-1,sizeof(dp));
dp[0][0]=0;
for (int i=1;i<=n;i++)
{
memcpy(c[i],c[i-1],sizeof(c[i]));
for (int j=a[i];j<=n;j+=j&-j)
c[i][j]++;
}

for (int i=1;i<=n;i++)
for (int j=1;j<=min(i,k);j++)
for (int x=0;x<i;x++)
if (dp[x][j-1]!=-1) dp[i][j]=max(dp[i][j],dp[x][j-1]+query(i,i)-query(x,i));

printf("%d\n",dp[n][k]);
return 0;
}
• star
首页