【模板】初级DP代码包

#include<bits/stdc++.h>
using namespace std;
int a[300010],b[300010],c[300010];
int tmp[300010];
int dp[100010],nnext[10010],f[1010][1010];
int n,m;
//最长不降子序列 O(n^2)
int LIS(int n)
{
    int ans=-1;
    for(int i=1;i<=n;i++)
    {
        dp[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]>=a[i]&&dp[j]+1>dp[i])
            {
                dp[i]=dp[j]+1;
                nnext[j]=i;
            }
        }
        ans=max(ans,dp[i]);
    }
    return ans;
}
//最长不降子序列 O(nlogn)
int d[1000010],len;
int LIS_nlogn(int n)
{
    memset(d,0,sizeof d);
    if(n==0)return 0;
	d[1]=tmp[1];len=1;
	for(int i=2;i<=n;i++)
	{
		if(tmp[i]>d[len])d[++len]=tmp[i];
		else
		{
			int at=upper_bound(d+1,d+len+1,tmp[i])-d;
			d[at]=tmp[i];
		}
	}
	return len;
}
//最长公共子序列 
int LCS(int n,int m)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i]==b[j])f[i][j]=f[i-1][j-1]+1;
            else f[i][j]=max(f[i][j-1],f[i-1][j]);
        }
    }
    return f[n][m];
}
//最长公共子序列（无重复）
int LCS_dif(int n,int m)
{
	int ans=0;
	map<int,int>mymap;
	for(int i=1;i<=n;i++)
	{
	    mymap[a[i]]=i;
	}
	int cnt=0;
	for(int j=1;j<=m;j++)
	{
		if(mymap.count(b[j]))
		{
			tmp[++cnt]=mymap[b[j]];
		}
	}
	return LIS_nlogn(cnt);
}
//最长回文字串 
vector<char>k;
int p[1000010];
int manacher(int n)
{
    k.push_back('$');
    for(int i=1;i<=n;i++)
    {
        k.push_back('#');
        k.push_back(a[i]);
    }
    k.push_back('#');
    k.push_back('\0');
    int len=k.size()-2;
    int mx=0,pi=1;
    for(int i=1;i<=len;i++)
    {
        if(i<mx)p[i]=min(mx-i,p[pi*2-i]);
        else p[i]=1;
        while(k[i+p[i]]==k[i-p[i]]&&i+p[i]<=len&&i-p[i]>=1)p[i]++;
        if(p[i]+i>mx)
        {
            pi=i;
            mx=p[i]+i;
        }
    }
    int maxn=-1;
    for(int i=1;i<=len;i++)
    {
        p[i]-=1;
        if(p[i]>maxn)maxn=p[i];
    }
    return maxn;
}
//01背包
int bag_01(int n,int C)
{
	memset(dp,0,sizeof dp);
	for(int i=1;i<=n;i++)
		for(int j=C;j>=1;j--)
			if(j>=c[i])
				dp[j]=max(dp[j],dp[j-c[i]]+b[i]);
	return dp[C];
} 
//完全背包
int bag_com(int n,int C)
{
	memset(dp,0,sizeof dp);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=C;j++)
			if(j>=c[i])
				dp[j]=max(dp[j],dp[j-c[i]]+b[i]);
	return dp[C];
} 
int main()
{
    
	return 0;
}