寒假冬训营递推专题题解

传送门

密码：202202060000

A - 上台阶2

分情况递归

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
const int mod=100003;
int dp[N];
int main()
{
  dp[0]=1,dp[1]=1,dp[2]=1;
  int n;
  scanf("%d",&n);
  for(int i=3;i<=n;++i){
    if(n>=5)
      dp[i]=(dp[i]+dp[i-1]+dp[i-3]+dp[i-5])%mod;
    else if(n>=3)
      dp[i]=(dp[i]+dp[i-1]+dp[i-3])%mod;
  }
  printf("%d\n",dp[n]);
  return 0;
}

B - 数字三角形

二维数组向上递推，推到最后maxSum [ 1 ] [ 1 ]就是最大的和

#include<bits/stdc++.h>
using namespace std;
int D[110][110];
int n;
int maxSum[110][110];
int main()
{
	int i,j; 
	cin>>n; 
	for(i=1;i<=n;i++) 
		for(j=1;j<=i;j++) 
			cin>>D[i][j];
	for(int i=1;i<=n;++i)
		maxSum[n][i]=D[n][i];
	for(int i=n-1;i>=1;--i) 
		for(int j=1;j<=i;++j) 
			maxSum[i][j]=max(maxSum[i+1][j],maxSum[i+1][j+1])+D[i][j];
	cout<<maxSum[1][1]<<endl;
}

用指针进行空间优化：

#include<bits/stdc++.h>
using namespace std;
#define MAX 101
int D[MAX][MAX];
int n;
int *maxSum;
int main()
{
	int i,j;
	cin>>n;
	for(i=1;i<=n;i++)
		for(j=1;j<=i;j++)
			cin >> D[i][j];
	maxSum = D[n]; //maxSum指向第n行
	for(int i=n-1;i>=1;--i)
		for(int j=1;j<=i;++j)
			maxSum[j]=max(maxSum[j],maxSum[j+1])+D[i][j];
	cout<<maxSum[1]<<endl; 
}

C - 矩阵取数问题

很经典的递推

#include<bits/stdc++.h>
using namespace std;
int a[510][510];
int dp[510][510];
int main()
{
	int N;
	cin>>N;
	for(int i=1;i<=N;i++)
	    for(int j=1;j<=N;j++)
		   cin>>a[i][j];
    for(int i=0;i<N;i++)  
       dp[i][0]=0;
	for(int i=0;i<N;i++)  
	   dp[0][i]=0;  
	for(int i=1;i<=N;i++)                  
	   for(int j=1;j<=N;j++)
	   	    dp[i][j]=max(dp[i][j-1],dp[i-1][j])+a[i][j]; 
	cout<<dp[N][N]<<endl;
	return 0;
}

D - 背包问题

01背包，不会的可以去学一下，推荐郭炜老师的算法课

#include<bits/stdc++.h>
using namespace std;
int f[101][10001];
int v[101];
int w[101];
int fun(int n,int m){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(j<w[i])//装不下
				f[i][j]=f[i-1][j];
			else
				f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);//装得下就可以比较装与不装哪个价值大
		}
		return f[n][m];
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>w[i]>>v[i];
	cout<<fun(n,m);
	return 0;
}

E - 完全背包

和01背包不同之处在于每件物品可以无限取，把01背包公式里的f [ i - 1 ] [ j - w [ i ] ]改成f [ i ] [ j - w [ i ] ]就行了

#include<bits/stdc++.h>
using namespace std;
int f[110][50010];
int v[10010]; 
int w[10010];
int fun(int n,int m)
{
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(j<w[i])
				f[i][j]=f[i-1][j];
			else
				f[i][j]=max(f[i-1][j],f[i][j-w[i]]+v[i]);//改成i就可以重复取当前的物品
		}
	}
		return f[n][m];
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>w[i]>>v[i];
	cout<<fun(n,m);
	return 0;
}

用一维数组进行空间优化：

#include<bits/stdc++.h>
using namespace std;
int f[50010];
int v[10010];
int w[10010];
int fun(int n,int m)
{
	for(int i=1;i<=n;i++){
		for(int j=w[i];j<=m;j++){
			f[j]=max(f[j],f[j-w[i]]+v[i]);
		}
	}
		return f[m];
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>w[i]>>v[i];
	cout<<fun(n,m);
	return 0;
}

F - 背包问题 V2

多重背包，介绍两种方法，首先三个循环下来肯定超时，所以我们可以尝试减少物品数量：

我们可以用二进制来化简

#include<bits/stdc++.h>
using namespace std;
int dp[50050];
int wi[10000],p[100000];
int main()
{
	int n,w;
	scanf("%d%d",&n,&w);
    int a,b,c,kp=1;
    for(int i=1;i<=n;i++){
    	scanf("%d%d%d",&a,&b,&c);
    	for(int j=1;c;j*=2){
    		if (c>=j){
				wi[kp]=a*j;
				p[kp++]=b*j;
				c-=j;
			}else{
				wi[kp]=a*c;
				p[kp++]=b*c;
				c=0;
			}
    	}
    }
    for(int i=1;i<kp;i++)
    	for(int j=w;j>=wi[i];j--)
    	 dp[j]=max(dp[j],dp[j-wi[i]]+p[i]);
    printf("%d\n",dp[w]);
    return 0;
}

还可以这样想：

如果一种物品的重量*数量>背包容量，就可以当做完全背包来看待

如果小于，我们再用二进制分解，这是一个模板

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 101;
const int SIZE = 50001;
int dp[SIZE];
int volume[MAXN], value[MAXN], c[MAXN];
int n, v;           // 总物品数，背包容量
// 01背包
void ZeroOnepark(int val, int vol) {
    for (int j = v ; j >= vol; j--)
    {
        dp[j] = max(dp[j], dp[j - vol] + val);
    }
}
// 完全背包
void Completepark(int val, int vol) {
    for (int j = vol; j <= v; j++)
    {
        dp[j] = max(dp[j], dp[j - vol] + val);
    }
}
// 多重背包
void Multiplepark(int val, int vol, int amount) {
    if (vol * amount >= v) {
        Completepark(val, vol);
    }else{
        int k = 1;
        while (k < amount) {
            ZeroOnepark(k * val, k * vol);
            amount -= k;
            k <<= 1;
        }
        if (amount > 0)
            ZeroOnepark(amount * val, amount * vol);
    }
}
int main()
{
    	cin >> n >> v; 
        for (int i = 1 ; i <= n ; i++)
            cin >> volume[i] >> value[i] >> c[i];// 费用，价值，数量
        for (int i = 1; i <= n; i++)
            Multiplepark(value[i], volume[i], c[i]);
        cout << dp[v] << endl;
    return 0;
}

G - 最长上升子序列

递推

#include<bits/stdc++.h>
using namespace std;
int a[1010];
int maxLen[1010];
int main()
{
	int N;
	cin>>N;
	for(int i=1;i<=N;++i){
	cin>>a[i];
	maxLen[i]=1;//初始化边界为1
	}
	for(int i=2;i<=N;++i)
		for(int j=1;j<i;++j)
			if(a[i]>a[j])
			maxLen[i]=max(maxLen[i],maxLen[j]+1);//上升就比较加1的情况和原来的情况，大小是不确定的，你可以找数验证
	cout<< *max_element(maxLen+1,maxLen+N+1);//输出数组中最大的元素
	return 0;
}

H - 最长公共子序列Lcs

这个题原本是一道O(mn)过不了的题，需要用bitset优化，有兴趣的可以去看看，推荐这个教程

改题了之后就好多了，这个题可以用二维数组递推，也可以用滚动数组(这里不再赘述)

先推出递推公式，再想办法推出一个原序列，我这里给大家推一下公式：

1 2	if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1;

如果i串和j串当前字符相等，那当前i，j 的状态就是没算上这个公共字符的i-1,j-1状态再加1

如果i串和j串当前字符不相等，我们要证明：

1	dp[i][j]=max(dp[i][j-1],dp[i-1][j]);

可以反证：

S1 [ i - 1] != s2 [ j - 1]时，MaxLen(S1,S2)不会比MaxLen(S1,S2j-1)和MaxLen(S1i-1,S2)两者之中任何一个小，也不会比两者都大。

MaxLen(S1,S2)不会比MaxLen(S1,S2j-1)和MaxLen(S1i-1,S2)两者之中任何一个小是很容易看出来的，因为MaxLen状态是递增的，下标大的状态不会小于下标小的状态。

后半句我们再反证一下：

也就是说，假设它比两者都大，那么对于MaxLen(S1,S2j-1)，S2j-1就算是最后一个公共字符了，否则MaxLen(S1,S2)就和MaxLen(S1,S2j-1)相等了；同理我们可以推出S1i-1也是最后一个公共字符，那么S1 [ i - 1]就和s2 [ j - 1]相等了，和前提S1 [ i - 1] != s2 [ j - 1]矛盾，至此得证。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int dp[maxn][maxn];
int main()
{
    char a[maxn],b[maxn],lcs[maxn];
    int i,j;
    cin>>a>>b;
    int lena=strlen(a),lenb=strlen(b);
    for(i=1;i<=lena;i++)
        for (j=1;j<=lenb;j++){
            if(a[i-1]==b[j-1])
			dp[i][j]=dp[i-1][j-1]+1;
            else
			dp[i][j]=max(dp[i][j-1],dp[i-1][j]);//比较难理解的地方
        }
    i=lena,j=lenb;
    int len=dp[lena][lenb];
    lcs[len]='\0';
    while(dp[i][j]){//倒推出一个最大公共子序列
        if (dp[i][j]==dp[i-1][j]) i--;
        else if (dp[i][j]==dp[i][j-1]) j--;
        else lcs[--len]=a[i-1],i--,j--;
    }
    printf("%s\n",lcs);
    return 0;
}

I - 石子合并

可以先去了解一下矩阵连乘，四边形优化

#include<bits/stdc++.h>
using namespace std;
const int N = 405;
int a[N],s[N],f[N][N],g[N][N];
int main()
{
    int n;
    cin>>n;
    for(int i = 1;i <= n;i++){
        cin>>a[i];
        a[i + n] = a[i];
    }
    for(int i = 1;i <= 2*n;i++) 
	s[i] = s[i-1] + a[i];
    for(int len = 2;len <= n;len++){
        for(int l = 1;l + len - 1 <= 2*n;l++){
            int r = l + len - 1;
            f[l][r] = 1e9;
            for(int k = l;k < r;k++){
                f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
                g[l][r] = max(g[l][r],g[l][k]+g[k+1][r]+s[r]-s[l-1]);
            }
        }
    }
    int res1 = 1e9,res2 = 0;
    for(int i = 1;i <= n;i++){
        res1 = min(res1,f[i][i+n-1]);
        res2 = max(res2,g[i][i+n-1]);
    }
    cout<<res1<<endl<<res2<<endl;
    return 0;
}

J - 循环数组最大子段和

这个题思路比较巧妙

如果不循环，那么状态转移方程：

if(dp[i-1]>0)
　　dp[i]=dp[i-1]+a[i];
else
　　dp[i]=a[i];

如果循环，可以认为不要中间一段最大负段和，要的是头部一段加尾部一段

求最大负段和，可以把数组所有值求个相反数，然后求最大正段和

注意: 这里说的负段和不是连续的负数，别误解了

最后，只需要比较头部一段加尾部一段的和与最大正段和的大小

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a[50005];
ll maxsum(ll a[]){//求最大段和
    ll sum=0,m=0;
    for(int i=0;i<n;i++){
        if(sum<0) 
            sum=a[i];
        else
            sum+=a[i];
        if(sum>m)
            m=sum;        
    }
    return m;
}
int main()
{
    cin>>n;
    ll sum=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    ll ans=maxsum(a);//正向求不循环的最大段和
    for(int i=0;i<n;i++)
        a[i]=-a[i];
    ll ans1=maxsum(a);//求序列最大的负段和的相反数
    cout<<max(ans,ans1+sum)<<endl;
    return 0;
}

K - 没有上司的舞会

树形dp,感兴趣的可以了解一下

#include<bits/stdc++.h>
using namespace std;
long long dp[100010][2],happy[100010],flag[100010];
vector <long long> son[100010],link[100010];
queue<long long>q;
void f(long long x)
{
 dp[x][0]=0;
 dp[x][1]=happy[x];
 for(int i=0;i<son[x].size();i++)
 {
  long long y=son[x][i];
  f(y);
  dp[x][0]+=max(dp[y][0],dp[y][1]);
  dp[x][1]+=dp[y][0];
 }	
}
int main()
{
 ios::sync_with_stdio(false);
 long long n,a,b;
 cin>>n;
 for(int i=1;i<=n;i++)
  cin>>happy[i];
 for(int i=1;i<n;i++)
 {
 	cin>>a>>b;
    link[a].push_back(b);
    link[b].push_back(a);
 }
 q.push(1);flag[1]=1;
 while(!q.empty())
 {
 	long long t=q.front(),tmp;
 	q.pop();
 	for(int i=0;i<link[t].size();i++)
 	 if(!flag[link[t][i]])
 	 {
 	  	tmp=link[t][i];
 	  	q.push(tmp);
 	  	flag[tmp]=1;
 	  	son[t].push_back(tmp);
	 }
 }
 f(1);
 cout<<max(dp[1][0],dp[1][1]);
 return 0; 
}

L - 滑雪

记忆化搜索

#include<bits/stdc++.h>
using namespace std;
int R,C,snow[105][105],sum;
int rmb[105][105];//记住搜索过的点，避免无用的重复搜索，节省大量时间
void dfs(int x,int y,int len){
	if(x<1||y<1||x>R||y>C)
	return;
	if(rmb[x][y]!=0){
		sum=max(sum,len+rmb[x][y]-1);
		return;
	}
	sum=max(sum,len);
	if(snow[x][y+1]<snow[x][y]) dfs(x,y+1,len+1);
	if(snow[x+1][y]<snow[x][y]) dfs(x+1,y,len+1);
	if(snow[x][y-1]<snow[x][y]) dfs(x,y-1,len+1);
	if(snow[x-1][y]<snow[x][y]) dfs(x-1,y,len+1);
}
int main()
{
	scanf("%d%d",&R,&C);
	int Max=-1;
	for(int i=1;i<=R;++i){
		for(int j=1;j<=C;++j){
			scanf("%d",&snow[i][j]);
		}
	}
	for(int i=1;i<=R;++i){
		for(int j=1;j<=C;++j){
			sum=0;
			dfs(i,j,1);
			rmb[i][j]=sum;
			Max=max(Max,sum);
		}
	}
	printf("%d",Max);
}