线性规划

动态规划一直是菜逼向巨神过渡的重要门槛，跃过了这道坎，即代表着您有了很强的逻辑思维能力，在中高端题面前能够获得充分的部分分

线规是动态规划中最简单的一种

常被用来求最值问题与计数问题

经典题

(LIS)

用(f[i])来记录长度为i的最长上升子序列的最后一位元素大小，
每加入一个一个新的值就在f序列中进行二分找到第一个大于等于该值的第一个元素

(LCS)

而(LCS)则是把每个(B)序列元素对应为(A)序列元素，将(AB)之间的元素形成一一映射，这样就把一个(LCS)问题转化为了(LIS)问题

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int p=1e5+5;

int a[p],b[p],map[p];
int f[p];

template<typename _T>
void read(_T &x)
{
	x =0;char s=getchar();int f=1;
	while(s<'0'||s>'9'){f=1;if(f=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
	x*=f;
}

signed main()
{
	int n;
	
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	read(n);
	
	for(int i=1;i<=n;i++)
	{
		read(a[i]);
		map[a[i]] = i;
	}
	for(int i=1;i<=n;i++)
	read(b[i]);
	
	memset(f,0x3f,sizeof(f));
	
	f[0] = 0;
	int len = 0;
	for(int i=1;i<=n;i++)
	{
		if(map[b[i]] > f[len]){f[++len] = map[b[i]];}
		else
		{
			int k = lower_bound(f+1,f+1+len,map[b[i]]) - f;
			f[k] = map[b[i]];
		}
	}
	
	cout<<len;
}

例：子串

考虑两个字符串划分为k段后完全匹配
仿照(LCS)的暴力式子列出了状态
(f[i][j][k][0/1])
代表A序列的前i个字符与B序列的前j个字符划分为k个字串且A的第i
个字符在或不在第k串中

[f[i][j][k][1] = f[i-1][j-1][k][1]+f[i-1][j-1][k-1][1]+f[i-1][j-1][k-1][0] ]

[f[i][j][k][0] = f[i-1][j][k][1] + f[i-1][j][k][0] ]

显然第一维我们可以滚动数组滚掉

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int base=29;

#define mod 1000000007 
#define int long long 

template<typename _T>
inline void read(_T &x)
{
	x=0;char s=getchar();int f=1;
	while(s<'0'||'9'<s){f=1;if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
	x*=f;
}

int f[2][205][205][3];


signed main()
{
	char a[1005];
	char b[1005];
	
	int n,m,s;
	
	read(n);
	read(m);
	read(s);

	scanf("%s%s",a+1,b+1);
	

	if(a[1] == b[1])
	f[1][1][1][1] =1;
	
	for(int i=2;i<=n;i++)
	{
		memset(f[i&1],0,sizeof(f[i&1]));
		
		if(a[i] == b[1])
		f[i&1][1][1][1] = 1;
		
		for(int j=1;j<i;j++)
		if(a[j] == b[1]) f[i&1][1][1][0]++;		
		
		for(int j=1;j<=m;j++)
			for(int k=1;k<=s;k++)
			{
				if(f[i&1][j][k][0] == 0)
				f[i&1][j][k][0] = f[i-1&1][j][k][0] + f[i-1&1][j][k][1],f[i&1][j][k][0]%=mod;
				if(a[i] == b[j] && f[i&1][j][k][1] == 0)
				f[i&1][j][k][1] = f[i-1&1][j-1][k-1][0] + f[i-1&1][j-1][k-1][1] + f[i-1&1][j-1][k][1],f[i&1][j][k][1]%=mod;
				
			}
	}
	
	int tot = f[n&1][m][s][1] + f[n&1][m][s][0];
	tot%=mod;
	
	cout<<((tot%mod)+mod)%mod;
}

题目集锦

(P4933)

本题也是一个线规计数类(dp)
因为和等差数列有关所以我们考虑把公差作为阶段来表示状态
(f[i][j][1/0])表示以(i)为结尾以(j)为公差，(1/0)表示是升序还是降序
由此得出状态转移方程

[f[i][j][1] = sum_{1≤k＜i}f[k][j][1](h_i = h_k+j) ]

[f[i][j][0] = sum_{1≤k＜i}f[k][j][0](h_i=h_k-j) ]

最后将两者相加再加上原本的电线杆的个数减去(sum_{1≤i≤n}f[i][0][0])就是总方案数

可以发现转移的时候需要枚举(k)来进行求和，这非常浪费时间，并且我们可以发现当(h-k=hi-d)才可以从(f(k))转移到(f(i))来，所以我们考虑维护一个数组(g[h])来表示高度为(h)的状态之和
这样就可以表示为
(f[i]= g[h_i - d])
(g[h_i] +=f[i])

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>


using namespace std;

#define int long long 

#define INF 1<<30
#define mod 998244353

const int p=2e4+5;

template<typename _T>
inline void read(_T &x)
{
	x=0;char s=getchar();int f=1;
	while(s<'0'||'9'<s){f=1;if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
	x*=f;
}

int h[p+5];
int g[p*2];
int f[p+5];

signed main()
{
	int n,v=0;
	read(n);
	for(int i=1;i<=n;i++)
	{
		read(h[i]);
		v=max(v,h[i]);
	}
	
	int tot = 0;
	
	for(int d=-v;d<=v;d++)
	{
		memset(g,0,sizeof(g));
		fill(f+1,f+1+n,1);
		for(int i=1;i<=n;i++)
		{
			if(h[i]>=d)
			f[i]+=g[h[i]-d];//f[k][d][1];
			f[i]%=mod;
			g[h[i]] += f[i];
			g[h[i]]%=mod;
		}
		for(int i=1;i<=n;i++)
		{
			tot+=f[i];//f[k][d][1];
			tot%=mod; 
		}
	}
	
	cout<<((tot-n*2*v)%mod+mod)%mod;
}

(P4767)

(qb)学堂的老师讲过这个题目，要求当作一种套路dp来记住
考虑(f[i][j])为前i所村庄修建j所邮局
其转移式为

[f[i][j] = f[k][j-1] + calc(k+1,i) ]

其中(calc(k+1,i))为(s[k+1])到(s[i])到(s[frac{k+1+i}{2}])的距离

复杂度为(O(PV^2))，显然题解中有更高端的做法，用四边形不等式优化,那我必然不会

如果我有一天也向他们一样向着更高的理想追求去了，可能就会把这里的坑给填了吧

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

int a[23333];
int f[233][2333];
int sum[233333];

inline int calc(int l,int r)
{
	int op=l+r>>1;
	return a[op]*(op-l+1)-sum[op]+sum[l-1]+abs(a[op]*(r-op+1)-sum[r]+sum[op-1]);
	
}

int main()
{
	int n,m;
	
	memset(f,0x3f,sizeof(f));
	
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	cin>>n>>m;
	
	int maxn=0;
	
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		maxn=max(maxn,a[i]);
	}
	
	for(int i=1;i<=n;i++)
	{
		sum[i]=sum[i-1]+a[i];
	}

	for(int i=1;i<=n;i++)
	{
		f[1][i]=calc(1,i);
	}
	
	for(int i=2;i<=m;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<j;k++)
	{
		f[i][j]=min(f[i][j],f[i-1][k] + calc(k+1,j));
	}
	
	cout<<f[m][n];
	
}

(P5858)

既然线规都说这么多了,再加一道曾经发过的又何妨

(f[i][j])代表此时已放入前i种原料，并且锅里有j种原料时最大值

[f[i][j] = max_{k=j-1}^{k≤min(w,j+s−1)}f[i-1][k] + a[i]*j ]

复杂度(O(nm^2))
可以发现随着j的上升k的上下边界也都在随之变化，那么就引导着我们进行单调队列优化

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

#define minn 5505

long long   a[minn];
long long   f[minn][minn]; 
long long   con[minn*2];
long long   que[minn*2];

int  main()
{
	long long   n,w,s;
	long long   maxn;
	
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	cin>>n>>w>>s;
	
	for(long long   i=1;i<=n;i++)
	cin>>a[i];
	
	memset(f,0xcf,sizeof(f));
	
	maxn=f[0][0];
	
	f[0][0]=0;
	
	for(long long   i=1;i<=n;i++)
	{
		int lef=1,rig=0;
		
		que[++rig] = f[i-1][w];
		con[rig] = w;
 		
		for(int k=w ;k ;k--)
		{
		
		while(lef <= rig && con[lef] > k + s - 1 ) lef++;
		
		while(lef <= rig && que[rig] < f[i-1][k-1]) rig--;
		
		con[++rig] = k-1;  	  
		que[rig] = f[i-1][k-1];
		
		f[i][k]= que[lef] + a[i] * k;
		
		}
	}
		
	for(long long   j=1;j<=w;j++)
	maxn=max(f[n][j],maxn);
	
	cout<<maxn;
}

(The End)

至此，考前习题集合到此就完结归档了，从数学专题到背包规划集合再至
线规集合，是我(NOIp)前集中停课一周所作

愿(NOIp rp++)

线规集合