Longest Common Subsequence

template<class T>
int LCS(T a[],int lena,T b[],int lenb)
{
    //int dp[2][lenb];
    for(int i=1,f=1;i<=lena;++i,f=!f)
        for(int j=1;j<=lenb;++j)
            if(a[i]==b[j])dp[f][j]=dp[!f][j-1]+1;
            else dp[f][j]=max(dp[!f][j],dp[f][j-1]);
    return dp[lena&1][lenb];
}

Longest Increasing Subsequence

int len[__];

int LIS(int a[],int n)
{
    int lis=0;
    for(int i=1;i<=n;++i)
    {
        int x=lower_bound(len+1,len+lis+1,a[i])-len;
        len[x]=a[i],lis=max(x,lis);
    }
    return lis;
}

决策单调队列

const int __=50005;
//id点决策[l,r]区间
struct des
{
    int id,l,r;
    des() {}
    des(int x,int y,int z):
        id(x),l(y),r(z) {}
};

int a[__];
fdeque<des>Q;
ll sum[__],dp[__],l;

ll sq(ll x){return x*x;}

//i点经k点决策
ll cal(int i,int k)
{
    return dp[k]+sq(i-k-1+sum[i]-sum[k]-l);
}

//二分
int bs(const des &t,int i)
{
    int l=max(t.l,i+1),r=t.r,ans=r;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(cal(mid,t.id)<=cal(mid,i))
            l=mid+1,ans=mid;
        else r=mid-1;
    }
    return ans;
}

int main()
{
    int n;sf("%d%lld",&n,&l);
    fup(i,1,n)
    {
        sf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    Q.pb(des(0,1,n));
    fup(i,1,n)
    {
        dp[i]=cal(i,Q.front().id);
        if(Q.front().r==i)Q.pop_front();
        if(i==n)break;
        Q.front().l=i+1;
        while(!Q.empty() && cal(Q.back().l,i)<cal(Q.back().l,Q.back().id))
            Q.pop_back();
        if(Q.empty())
        {
            Q.pb(des(i,i+1,n));
            continue;
        }
        des &t=Q.back();
        int r=bs(t,i);
        Q.pop_back();
        Q.pb(des(t.id,t.l,r));
        if(r!=n)Q.pb(des(i,r+1,n));
    }
    pf("%lld\n",dp[n]);
    return 0;
}

区间dp

O(n³)

for(int l=2;l<=n;l++)
    for(int i=1,j=i+l-1;j<=n;i++,j++)
        for(int k=i;k<j;k++)
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);

区间单调性:

四边形不等式:

如果w满足上面两个性质, 那么dp也满足四边形不等式

定义s[i][j]为dp[i][j]的决策点, 如果dp满足四边形不等式, 那么:

O(n²)

for(int l=2;l<=n;l++)
    for(int i=1,j=i+l-1;j<=n;i++,j++)
        for(int k=s[i][j-1];k<=min(j-1,s[i+1][j]);k++)
        {
            int x=dp[i][k]+dp[k+1][j]+w[i][j];
            if(x<=dp[i][j])s[i][j]=k,dp[i][j]=x;
        }

数位dp:

struct DigitalDynamicProgramming
{
    int bit[20],a[20];
    ll dp[20][20];

    DigitalDynamicProgramming() {memset(dp,-1,sizeof(dp));}

    ll dfs(int len,int sum,bool lim)
    {
        if(!len)return 1;
        if(!lim && ~dp[len][sum])return dp[len][sum];
        int r=lim?bit[len]:9;
        if(len<=(sum-1)/2)
            if(a[sum-len]>r)return 0;
            else return dfs(len-1,sum,lim && a[sum-len]==r);
        ll res=0;
        for(int i=(len==sum-1);i<=r;++i)
        {
            a[len]=i;
            res+=dfs(len-1,sum,lim && i==bit[len]);
        }
        if(lim)return res;
        return dp[len][sum]=res;
    }

    ll cal(ll x)
    {
        if(x<0)return 0;
        int idx=0;
        for(;x;x/=10)bit[++idx]=x%10;
        ll res=0;
        for(int i=1;i<=idx;++i)
            res+=dfs(i,i+1,i==idx);
        return res+1;
    }
}dp;