[数据结构与算法]HENAU冬令营-递推专题

资料链接：动态规划-背包问题
石子合并问题
树形dp

动态规划

A - 上台阶2

思路：简单递推
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=100003;
ll n,dp[maxn];
int main(){
    dp[1]=1;
    dp[3]=1;
    dp[5]=1;
    dp[0]=1;
    cin>>n;
    for(int i=2;i<=n;i++){
        if(i>=3&&i>=5){
            dp[i]=dp[i-1]+dp[i-3]+dp[i-5];
        }else{
           if(i>=3){
                dp[i]=dp[i-1]+dp[i-3];
           }else{
                dp[i]=dp[i-1];
           }
        }
        dp[i]%=mod;
    }
    cout<<dp[n];
    return 0;
}

B - 数字三角形

思路：和杨辉三角差不多
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=100003;
ll n;
ll dp[110][110],a[110][110];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            dp[i][j]=max(dp[i-1][j-1]+a[i][j],dp[i-1][j]+a[i][j]);
            //cout<<dp[i][j]<<" ";
        }
        //cout<<endl;
    }
    ll ma=0;
    for(int i=1;i<=n;i++){
        ma=max(dp[n][i],ma);
    }
    cout<<ma;
    return 0;
}

C - 矩阵取数问题

思路：和上一题差不多
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=100003;
ll n;
ll dp[510][510],a[510][510];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=max(dp[i][j-1]+a[i][j],dp[i-1][j]+a[i][j]);
            //cout<<dp[i][j]<<" ";
        }
        //cout<<endl;
    }
    ll ma=0;
    for(int i=1;i<=n;i++){
        ma=max(dp[n][i],ma);
    }
    cout<<ma;
    return 0;
}

经典动态规划

D - 背包问题

思路：01背包问题
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=100003;
ll n,wi;
ll w[maxn],v[maxn];
ll dp[10010];
int main(){
    cin>>n>>wi;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=wi;j>=w[i];j--){
            dp[j]=max(dp[j-w[i]]+v[i],dp[j]);
        }
        //cout<<dp[wi]<<" ";
    }
    cout<<dp[wi];
    return 0;
}

E - 完全背包

思路：完全背包问题与01背包的区别在于可不可以重复拿
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=100003;
ll n,wi;
ll w[maxn],v[maxn];
ll dp[50010];
int main(){
    cin>>n>>wi;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=w[i];j<=wi;j++){
            dp[j]=max(dp[j-w[i]]+v[i],dp[j]);
        }
        //cout<<dp[wi]<<" ";
    }
    cout<<dp[wi];
    return 0;
}

F - 背包问题 V2

思路：这里可以用多重背包拆成01背包求解的思想，不过在拆的时候不能将Cn拆成1+1+1+1+1+1…+1的形式。这么做会超时。
应该将Cn拆成 Cn=1+2+4+8+…+(Cn-sum)。这里sum表示前面的数字之和，例如 按照规律加到第m个数，发现已经大于Cn，那么sum就表示从 1+2+4+8+…+ 2^(m-2)。 我们可以检验， 在[1,Cn]中任意的数 我们都可以在这个序列中找到若干数相加得到。拆分结束后我们就可以按照01背包求解。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=100003;
ll n,wi;
ll w[maxn],v[maxn],c[maxn];
ll dp[50010];
ll cnt;
int main(){
    cin>>n>>wi;
    for(int i=1;i<=n;i++){
        ll wz,vz,cz;
        cin>>wz>>vz>>cz;
        for(int j=1;j<cz;j=j<<1){
            w[++cnt]=j*wz;
            v[cnt]=j*vz;
            cz-=j;
        }
        w[++cnt]=cz*wz;
        v[cnt]=cz*vz;

    }
    for(int i=1;i<=cnt;i++){
        //cout<<w[i]<<" "<<v[i]<<endl;
        for(int j=wi;j>=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    //cout<<dp[wi]<<" ";
    }
    cout<<dp[wi];
    return 0;
}

G - 最长上升子序列

思路：经典dp问题
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=100003;
ll n;
ll a[maxn];
ll dp[maxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        dp[i]=1;
    }
    //dp[1]=1;
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(a[i]>a[j]){
                dp[i]=max(dp[j]+1,dp[i]);
            }
        }
        ans =max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}

H - 最长公共子序列

暴力不太行，后续给出

I - 石子合并

思路：经典问题，可以看资料链接
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=70010;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=100003;
ll n,m;
ll a[maxn],sum[maxn];
ll d[210][210],p[210][210];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
        //sum[i]=sum[i-1]+a[i];
        //d[i][i]=p[i][i]=0;
    }
    for(int i=1;i<=2*n;i++){
        sum[i]=sum[i-1]+a[i];
    }
    for(int len=2;len<=n;len++){
        for(int l=1;l<=(2*n-len+1);l++){
            int r=l+len-1;
            d[l][r]=0;
            p[l][r]=inf;
            ll tmp=sum[r]-sum[l-1];
            for(int k=l;k<r;k++){
                d[l][r]=max(d[l][r],d[l][k]+d[k+1][r]+tmp);
                p[l][r]=min(p[l][r],p[l][k]+p[k+1][r]+tmp);
            }
            //cout<<p[l][r]<<" "<<l<<" "<<r<<endl;
        }
    }
    ll mi=inf,ma=0;
    for(int i=1;i<=n;i++){
        mi=min(mi,p[i][i+n-1]);
        ma=max(ma,d[i][i+n-1]);
    }
    cout<<mi<<endl;
    cout<<ma<<endl;
    return 0;
}

J - 循环数组最大子段和

思路：题目要求是可以循环，分为两种情况：
1、没有循环，找到了最大的子段。
2、循环了，找到了最大的子段。
第一种情况很简单，第二种解决方法就是找到最小的子段，数组和减去最小子段和，就是最大循环子段和。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=50100;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=100003;
ll n,m;
ll a[maxn];
ll dp[maxn];
ll sum=0;
int main(){
    cin>>n;
    ll ma=0;
    ll mi=inf;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    for(int i=1;i<=n;i++){
        if(dp[i-1]<0){
            dp[i]=a[i];
        }else{
            dp[i]=dp[i-1]+a[i];
        }
        ma=max(dp[i],ma);
    }
    for(int i=1;i<=n;i++){
        if(dp[i-1]>0){
            dp[i]=a[i];
        }else{
            dp[i]=dp[i-1]+a[i];
        }
        mi=min(dp[i],mi);
    }
    mi=sum-mi;
    ma=max(mi,ma);
    cout<<ma<<endl;
    return 0;
}

特殊动态规划

K - 没有上司的舞会

思路：树上dp入门
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=100010;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=100003;
vector<ll> g[maxn];
ll vis[maxn];
ll h[maxn];
ll n;
ll f[maxn][10];
ll v[maxn];
void dfs(ll x){
    v[x]=1;
    f[x][0]=0;
    f[x][1]=h[x];
    for(int i=0;i<g[x].size();i++){
        ll son=g[x][i];
        if(v[son])continue;
        dfs(son);
        f[x][0]+=max(f[son][0],f[son][1]);
        f[x][1]+=f[son][0];
    }
    return ;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    for(int i=1;i<n;i++){
        ll x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    ll ans=0;
    dfs(1);
    ans=max(f[1][0],f[1][1]);
    cout<<ans;
    return 0;
}

L - 滑雪

思路：迷宫改编，类似树形dp
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=100010;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=100003;
ll n,m;
ll a[110][110];
ll dp[110][110];
ll d[2][4]={{0,1,0,-1},{1,0,-1,0}};
ll dfs(ll x,ll y){
    if(dp[x][y])return dp[x][y];
    dp[x][y]=1;
    for(int i=0;i<4;i++){
        ll dx=x+d[0][i];
        ll dy=y+d[1][i];
        if(dx<1||dx>n||dy<1||dy>m)continue;
        if(a[x][y]<a[dx][dy]){
            dfs(dx,dy);
            dp[x][y]=max(dp[x][y],dp[dx][dy]+1);
        }
    }
    return dp[x][y];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dfs(i,j);
            ans=max(ans,dp[i][j]);
        }
    }
    cout<<ans;
    return 0;
}