1012.String-Distance

标签：dp求LCS

因为插入操作可以被删除操作替代，所以问题也就转化成求A、B两串的最长公共子序列(LCS)

先预处理出g[i][c]表示[ai,ai+1,…,an]中第一个字符c的下标

dp[i][j]表示用B串前i位匹配到j个字符时在A串中最小的位置

然后就可以O(m^2)转移了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+5,INF=0x3f3f3f3f;

int T,q,l,r;

char s[N],t[25];

vector<int>G[30];

int dp[25][25];
int g[N][30];
int ans[N];
struct query{
    int l,r,id;
}Q[N];
int main()
{
    cin>>T;
    while(T--)
    {
        scanf("%s",s+1);
        scanf("%s",t+1);
        int ls=strlen(s+1),lt=strlen(t+1);
        for (int j=0;j<=25;j++) g[ls+1][j]=INF;
        for (int i=ls;i>=1;i--)
        {
            for (int j=0;j<=25;j++)
                if ((s[i]-'a')==j) g[i][j]=i;
                else
                {
                    g[i][j]=g[i+1][j];
                }
        }
        cin>>q;
        while(q--)
        {
            scanf("%d%d",&l,&r);
            memset(dp,INF,sizeof(dp));
            int mx=0;
            for (int i=0;i<=lt;i++) dp[i][0]=l-1;
            for (int i=1;i<=lt;i++)
            {
                if (g[dp[i-1][0]+1][t[i]-'a']<=r)
                dp[i][1]=min(dp[i-1][1],g[dp[i-1][0]+1][t[i]-'a']);
                else
                    dp[i][1]=dp[i-1][1];
                if (dp[i][1]!=INF) mx=max(mx,1);
            }
            for (int i=2;i<=lt;i++)
                for (int j=2;j<=i;j++)
                {
                    if (dp[i-1][j-1]!=INF && g[dp[i-1][j-1]+1][t[i]-'a']<=r)
                    dp[i][j]=min(dp[i-1][j],g[dp[i-1][j-1]+1][t[i]-'a']);
                    else
                        dp[i][j]=dp[i-1][j];
                    if (dp[i][j]!=INF) mx=max(mx,j);
                }
            printf("%d\n",r-l+1+lt-2*mx);
        }
    }
    return 0;
}

1005.New-Equipments

把问题转换成n个二次函数图像，比较重要的是观察到每个工人只需要考虑对称轴附近的50个数，那么最多只需要考虑2500个数就可以了。

把所有工人作为一个点和源点连边，把需要考虑的数与汇点连边，再把每个工人与其需要考虑的数连边，距离为花费。

然后开始跑最小费用最大流，每找到一条增广路就记录一次答案。

#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" : "<<x<<endl;
using namespace std;
typedef long long ll;

const int MAXN=11000;

int T,n,m,top;

ll ans;

bool vis[MAXN];

int s,t,pre[MAXN],last[MAXN],flow[MAXN],maxflow;

ll dis[MAXN],mincost;

struct Edge{
    int to,next,flow;//flow流量 dis花费
    ll dis;
}edge[MAXN];
int head[MAXN],num_edge;
queue <int> q_SPFA;
void add_edge(int from,int to,int flow,ll dis)
{
    edge[++num_edge].next=head[from];
    edge[num_edge].to=to;
    edge[num_edge].flow=flow;
    edge[num_edge].dis=dis;
    head[from]=num_edge;
}
bool spfa(int s,int t)
{
    memset(dis,0x7f,sizeof(dis));
    memset(flow,0x7f,sizeof(flow));
    memset(vis,0,sizeof(vis));
    q_SPFA.push(s); vis[s]=1; dis[s]=0; pre[t]=-1;
    while (!q_SPFA.empty())
    {
        int now=q_SPFA.front();
        q_SPFA.pop();
        vis[now]=0;
        for (int i=head[now]; i!=-1; i=edge[i].next)
        {
            if (edge[i].flow>0 && dis[edge[i].to]>dis[now]+edge[i].dis)//正边
            {
                dis[edge[i].to]=dis[now]+edge[i].dis;
                pre[edge[i].to]=now;
                last[edge[i].to]=i;
                flow[edge[i].to]=min(flow[now],edge[i].flow);
                if (!vis[edge[i].to])
                {
                    vis[edge[i].to]=1;
                    q_SPFA.push(edge[i].to);
                }
            }
        }
    }
    return pre[t]!=-1;
}
void MCMF()
{
    while (spfa(s,t))
    {
        int now=t;
        maxflow+=flow[t];
        mincost+=1ll*flow[t]*dis[t];
        top++;
        printf("%lld%c",mincost,top==n?'\n':' ');
        if (top==n) return;
        while (now!=s)
        {
            edge[last[now]].flow-=flow[t];
            edge[last[now]^1].flow+=flow[t];
            now=pre[now];
        }
    }
}

ll a[55],b[55],c[55];

set<int>S;
vector<int>G[55];
map<int,int>ord;

void init()
{
    top=0;
    num_edge=-1;
    memset(head,-1,sizeof(head));
    memset(edge,0,sizeof(edge));
    S.clear();
    for (int i=1;i<=n;i++) G[i].clear();
    ord.clear();
    maxflow=mincost=0;
}

void sol()
{
    cin>>n>>m;
    init();
    for (int i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
        int mid=b[i]/(-2*a[i]);
        int l=mid-25,r=mid+25;
        if (r<1)
        {
            l=1,r=min(m,50);
        }
        else
        {
            if (l>m)
            {
                r=m;l=max(1,r-49);
            }
            else
            {
                if (l<1)
                {
                    r+=1-l;
                    l=1;
                }
                if (r>m)
                {
                    l-=r-m;
                    r=m;
                }
                if (l<1) l=1;
            }
        }
        for (int j=l;j<=r;j++)
        {
            S.insert(j);
            G[i].push_back(j);
        }
    }
    s=0,t=n+S.size()+1;
    for (int i=1;i<=n;i++)
    {
        add_edge(s,i,1,0);
        add_edge(i,s,0,0);
    }
    int tmp=0;
    for (auto x:S)
    {
        ord[x]=++tmp;
        add_edge(n+ord[x],t,1,0);
        add_edge(t,n+ord[x],0,0);
    }

    for (int i=1;i<=n;i++)
    {
         for (auto to:G[i])
        {
            add_edge(i,n+ord[to],1,(a[i]*to*to+b[i]*to+c[i]));
             add_edge(n+ord[to],i,0,-1ll*(a[i]*to*to+b[i]*to+c[i]));
        }
    }
    MCMF();
}
int main()
{
    cin>>T;
    while(T--)
        sol();
    return 0;
}