【Codeforces717G】Underfail Hash + 最大费用最大流

You have recently fallen through a hole and, after several hours of unconsciousness, have realized you are in an underground city. On one of your regular, daily walks through the unknown, you have encountered two unusually looking skeletons called Sanz and P’pairus, who decided to accompany you and give you some puzzles for seemingly unknown reasons.

One day, Sanz has created a crossword for you. Not any kind of crossword, but a 1D crossword! You are given m words and a string of length n. You are also given an array p, which designates how much each word is worth — the i-th word is worth pi points. Whenever you find one of the m words in the string, you are given the corresponding number of points. Each position in the crossword can be used at most x times. A certain word can be counted at different places, but you cannot count the same appearance of a word multiple times. If a word is a substring of another word, you can count them both (presuming you haven’t used the positions more than x times).

In order to solve the puzzle, you need to tell Sanz what’s the maximum achievable number of points in the crossword. There is no need to cover all postions, just get the maximal score! Crossword and words contain only lowercase English letters.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 500) — the length of the crossword. The second line contains the crossword string. The third line contains a single integer m (1 ≤ m ≤ 100) — the number of given words, and next m lines contain description of words: each line will have a string representing a non-empty word (its length doesn't exceed the length of the crossword) and integer pi (0 ≤ pi ≤ 100). Last line of the input will contain x (1 ≤ x ≤ 100) — maximum number of times a position in crossword can be used.

Output

Output single integer — maximum number of points you can get.

Example

input

6
abacba
2
aba 6
ba 3
3

output

Note

For example, with the string "abacba", words "aba" (6 points) and "ba" (3 points), and x = 3, you can get at most 12 points - the word "aba" appears once ("abacba"), while "ba" appears two times ("abacba"). Note that for x = 1, you could get at most 9 points, since you wouldn’t be able to count both "aba" and the first appearance of "ba".

Solution

题目大意：给定一个长度为N的模板串，以及M个短串，每个短串有一个价值c，用一个短串完全匹配模板串的区间，可以得到短串的价值。每个短串可以匹配任意次，模板串的每个位置，只能匹配K次。求最大价值。

这道题还是比较容易想到的

首先把所有短串去和大串匹配，得到每个小串的完全匹配的区间。然后套用费用流经典建图。

这个过程可以暴力，Hash，AC自动机，KMP...

然后对于这个区间$[l,r]$，我们连边$<l,r+1>,cap=1,cost=c$ ，这里连边$<l,r+1>$是控制区间左闭右开，否则会出现负环。

然后连$<S,1>,cap=K,cost=0$以及$<N,T>,cap=K,cost=0$ ，前一个位置向后一个位置连边$<i,i+1>,cap=K,cost=0$

然后跑$S->T$的最大费用最大流就是答案。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
#define MAXN 510
int N,M,K,c[101];
char s[MAXN],ss[101][202];
namespace Hash
{
    #define base 131
    #define ULL unsigned long long
    ULL hash[MAXN],bin[MAXN];
    void Hashtable()
    {
        bin[0]=1; for (int i=1; i<=N; i++) bin[i]=bin[i-1]*base;
        for (int i=1; i<=N; i++) hash[i]=hash[i-1]*base+s[i];
    }
    ULL GetHash(int l,int r) {return hash[r]-hash[l-1]*bin[r-l+1];}
    ULL Hashit(char st[])
    {
        ULL re=0; int len=strlen(st+1);
        for (int i=1; i<=len; i++) re=re*base+st[i];
        return re;
    }
}
using namespace Hash;
namespace CostFlow
{
    #define INF 0x7fffffff
    #define MAXM 100010
    struct EdgeNode{int next,to,cap,cost,from;}edge[MAXM<<1];
    int head[MAXN],cnt=1;
    inline void AddEdge(int u,int v,int w,int c) {cnt++; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].cap=w; edge[cnt].cost=c; edge[cnt].from=u;}
    inline void InsertEdge(int u,int v,int w,int c) {AddEdge(u,v,w,c); AddEdge(v,u,0,-c);}
    int S,T,Cost,dis[MAXN],visit[MAXN],mark[MAXN];
    queue<int>q;
    inline bool SPFA()
    {
        for (int i=S; i<=T; i++) dis[i]=-INF;
        q.push(S); visit[S]=1; dis[S]=0;
        while (!q.empty())
            {
                int now=q.front(); q.pop(); visit[now]=0;
                for (int i=head[now]; i; i=edge[i].next)
                    if (edge[i].cap && dis[edge[i].to]<dis[now]+edge[i].cost)
                        {
                            dis[edge[i].to]=dis[now]+edge[i].cost;
                            if (!visit[edge[i].to]) q.push(edge[i].to),visit[edge[i].to]=1;
                        }
            }
        return dis[T]!=-INF;
    }
    inline int dfs(int now,int low)
    {
        mark[now]=1;
        if (now==T) return low;
        int w,used=0;
        for (int i=head[now]; i; i=edge[i].next)
            if (!mark[edge[i].to] && edge[i].cap && dis[edge[i].to]==dis[now]+edge[i].cost)
                {
                    w=dfs(edge[i].to,min(low-used,edge[i].cap));
                    edge[i].cap-=w; edge[i^1].cap+=w; Cost+=w*edge[i].cost; used+=w;
                    if (used==low) return low;
                }
        return used;
    }
    inline int zkw()
    {
        int re=0;
        while (SPFA())
            {
                mark[T]=1;
                while (mark[T])
                    memset(mark,0,sizeof(mark)),re+=dfs(S,INF);
            }
        return re;
    }
    inline void BuildGraph()
    {
        S=0,T=N+1;
        Hash::Hashtable();
        InsertEdge(S,1,K,0); InsertEdge(N,T,K,0);
        for (int i=1; i<=N-1; i++) InsertEdge(i,i+1,K,0);
        for (int i=1; i<=M; i++)
            {
                ULL _hash=Hash::Hashit(ss[i]); int l=strlen(ss[i]+1);
                for (int j=1; j+l-1<=N; j++) 
                    if (Hash::GetHash(j,j+l-1)==_hash) InsertEdge(j,j+l,1,c[i]);
            }
//        for (int i=2; i<=cnt; i+=2) printf("%d %d %d %d
",edge[i].from,edge[i].to,edge[i].cap,edge[i].cost);
    }        
}
int main()
{
    N=read(); scanf("%s",s+1);
    M=read();
    for (int i=1; i<=M; i++) scanf("%s",ss[i]+1),c[i]=read();
    K=read();
    CostFlow::BuildGraph();
    CostFlow::zkw();
    printf("%d
",CostFlow::Cost);
    return 0;
}

Codeforces上的数据真是太小了...这个题暴力都能跑的那么快...