C++动态规划-线性DP

这是一套C++线性DP题目的答案。如果需要题目，请私信我，我将会更新题干

P1:单子序列最大和

#include <bits/stdc++.h>
using namespace std;
int n,A,B,C;
int a[200005];
int s[200005];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>A>>B>>C;for(int i=1; i<=n; i++){int tmp=((long long)A*i*i+B*i+C)%20000;a[i]=tmp-10000;}int ans=INT_MIN;for(int i=1; i<=n; i++){s[i]=max(s[i-1]+a[i],a[i]);ans=max(ans,s[i]);}cout<<ans;return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,A,B,C;
int a[200005];
int s[200005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>A>>B>>C;
    for(int i=1; i<=n; i++)
    {
        int tmp=((long long)A*i*i+B*i+C)%20000;
        a[i]=tmp-10000;
    }
    int ans=INT_MIN;
    for(int i=1; i<=n; i++)
    {
        s[i]=max(s[i-1]+a[i],a[i]);
        ans=max(ans,s[i]);
    }
    cout<<ans;
    return 0;
}
P2 跳格子

#include <bits/stdc++.h>
using namespace std;
int n,A,B,C;
int a[100005];
int s[100005];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>A>>B>>C;for(int i=1; i<=n; i++){int tmp=((long long)A*i*i+B*i+C)%20000;a[i]=tmp-10000;}
//	for(int i=1; i<=n; i++) cout<<a[i]<<" ";
//	cout<<'\n';int ans=INT_MIN;for(int i=1; i<=n; i++){s[i]=max(s[i-1],s[i-2])+a[i-1];}cout<<s[n];return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,A,B,C;
int a[100005];
int s[100005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>A>>B>>C;
    for(int i=1; i<=n; i++)
    {
        int tmp=((long long)A*i*i+B*i+C)%20000;
        a[i]=tmp-10000;
    }
//    for(int i=1; i<=n; i++) cout<<a[i]<<" ";
//    cout<<'\n';
    int ans=INT_MIN;
    for(int i=1; i<=n; i++)
    {
        s[i]=max(s[i-1],s[i-2])+a[i-1];
    }
    cout<<s[n];
    return 0;
}
跳格子2

#include <bits/stdc++.h>
using namespace std;
int n,A,B,C;
int a[100005];
int s[100005];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>A>>B>>C;for(int i=1; i<=n; i++){int tmp=((long long)A*i*i+B*i+C)%20000;a[i]=tmp-10000;}
//	for(int i=1; i<=n; i++) cout<<a[i]<<" ";
//	cout<<'\n';for(int i=1; i<=n; i++) s[i]=min(s[i-1],s[i-2])+a[i];cout<<s[n];return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,A,B,C;
int a[100005];
int s[100005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>A>>B>>C;
    for(int i=1; i<=n; i++)
    {
        int tmp=((long long)A*i*i+B*i+C)%20000;
        a[i]=tmp-10000;
    }
//    for(int i=1; i<=n; i++) cout<<a[i]<<" ";
//    cout<<'\n';
    for(int i=1; i<=n; i++) s[i]=min(s[i-1],s[i-2])+a[i];
    cout<<s[n];
    return 0;
}
[动态规划]数塔

#include <bits/stdc++.h>
using namespace std;
int n;
int a[105][105];
int s[105][105];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);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++) s[i][j]=max(s[i-1][j],s[i-1][j-1])+a[i][j];}int ans=INT_MIN;for(int i=1; i<=n; i++) ans=max(s[n][i],ans);cout<<ans;return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n;
int a[105][105];
int s[105][105];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    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++) s[i][j]=max(s[i-1][j],s[i-1][j-1])+a[i][j];
    }
    int ans=INT_MIN;
    for(int i=1; i<=n; i++) ans=max(s[n][i],ans);
    cout<<ans;
    return 0;
}
方格取数1

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[105][105];
long long s[105][105];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=0; i<=n+1; i++){for(int j=0; j<=m+1; j++) s[i][j]=INT_MAX;}for(int i=1; i<=n; i++){for(int j=1; j<=m; j++) cin>>a[i][j];}s[1][1]=a[1][1];for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){if(!(i==1&&j==1)) s[i][j]=min(s[i-1][j],s[i][j-1])+a[i][j];}}/*for(int i=1; i<=n; i++){for(int j=1; j<=m; j++) cout<<setw(2)<<s[i][j]<<" ";cout<<'\n';}*/cout<<s[n][m];return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[105][105];
long long s[105][105];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=0; i<=n+1; i++)
    {
        for(int j=0; j<=m+1; j++) s[i][j]=INT_MAX;
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++) cin>>a[i][j];
    }
    s[1][1]=a[1][1];
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(!(i==1&&j==1)) s[i][j]=min(s[i-1][j],s[i][j-1])+a[i][j];
        }
    }
    /*
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++) cout<<setw(2)<<s[i][j]<<" ";
        cout<<'\n';
    }
    */
    cout<<s[n][m];
    return 0;
}
take

#include <bits/stdc++.h>
using namespace std;
int n;
int a[55],s[55];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1; i<=n; i++) cin>>a[i];int ans=INT_MIN;for(int i=1; i<=n; i++){s[i]=INT_MIN;for(int j=2; j<=i; j++) s[i]=max(s[i-j]+a[i],s[i]);if(i==1) s[i]=a[i];ans=max(ans,s[i]);//cout<<s[i]<<" ";}cout<<ans;return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n;
int a[55],s[55];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    int ans=INT_MIN;
    for(int i=1; i<=n; i++)
    {
        s[i]=INT_MIN;
        for(int j=2; j<=i; j++) s[i]=max(s[i-j]+a[i],s[i]);
        if(i==1) s[i]=a[i];
        ans=max(ans,s[i]);
        //cout<<s[i]<<" ";
    }
    cout<<ans;
    return 0;
}
大盗阿福（开long long）

#include <bits/stdc++.h>
using namespace std;
int n,x,y,z;
long long a[100005];
long long s[100005];
long long b[100005];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>x>>y>>z;for(int i=1; i<=n; i++) a[i]=((long long)i*i*x+i*y+z)%1000+1;long long ans=LONG_LONG_MIN;
//	for(int i=1; i<=n; i++) cin>>a[i];
//	cout<<'\n';for(int i=1; i<=n; i++){s[i]=b[i-2]+a[i];if(s[i]>ans) ans=s[i];if(s[i]>b[i-1]) b[i]=s[i];else b[i]=b[i-1];//cout<<s[i]<<" ";}cout<<ans;return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,x,y,z;
long long a[100005];
long long s[100005];
long long b[100005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>x>>y>>z;
    for(int i=1; i<=n; i++) a[i]=((long long)i*i*x+i*y+z)%1000+1;
    long long ans=LONG_LONG_MIN;
//    for(int i=1; i<=n; i++) cin>>a[i];
//    cout<<'\n';
    for(int i=1; i<=n; i++)
    {
        s[i]=b[i-2]+a[i];
        if(s[i]>ans) ans=s[i];
        if(s[i]>b[i-1]) b[i]=s[i];
        else b[i]=b[i-1];
        //cout<<s[i]<<" ";
    }
    cout<<ans;
    return 0;
}
Leapcow

#include <bits/stdc++.h>
using namespace std;
int n,e,b;
bool g[40005];
int s[40005];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>e>>n>>b;for(int i=1; i<=b; i++){int x;cin>>x;g[x]=1;}for(int i=1; i<=e; i++){s[i]=INT_MAX;for(int j=max(0,i-n); j<=i; j++){if(g[j]==1) continue;s[i]=min(s[i],s[j]+1);}}cout<<s[e];return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,e,b;
bool g[40005];
int s[40005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>e>>n>>b;
    for(int i=1; i<=b; i++)
    {
        int x;
        cin>>x;
        g[x]=1;
    }
    for(int i=1; i<=e; i++)
    {
        s[i]=INT_MAX;
        for(int j=max(0,i-n); j<=i; j++)
        {
            if(g[j]==1) continue;
            s[i]=min(s[i],s[j]+1);
        }
    }
    cout<<s[e];
    return 0;
}
乘车费用

#include <bits/stdc++.h>
using namespace std;
long long a[15];
long long s[105];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);for(int i=1; i<=10; i++) cin>>a[i];int n;cin>>n;for(int i=1; i<=n; i++){if(!s[i]) s[i]=LONG_LONG_MAX;for(int j=1; j<=10; j++){int now=s[i-j]+a[j];if(s[i]>now) s[i]=now;}}cout<<s[n];return 0;
}

#include <bits/stdc++.h>
using namespace std;
long long a[15];
long long s[105];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    for(int i=1; i<=10; i++) cin>>a[i];
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        if(!s[i]) s[i]=LONG_LONG_MAX;
        for(int j=1; j<=10; j++)
        {
            int now=s[i-j]+a[j];
            if(s[i]>now) s[i]=now;
        }
    }
    cout<<s[n];
    return 0;
}
双子序列最大和

#include <bits/stdc++.h>
using namespace std;
int a[1005];
int ps[1005];
int ls[1005],rs[1005];
int main()
{/*1.生成 2.前缀和3.1~n左序列（正常生成）4.n~1右序列（正常生成）5.1~n-1左右序列匹配 图 . . . . .---   ---左    右 */int n,A,B,C;cin>>n>>A>>B>>C;for(int i=1; i<=n; i++){ls[i]=INT_MIN;rs[i]=INT_MIN;long long tmp=((long long)A*i*i+B*i+C)%20000;a[i]=tmp-10000;}for(int i=1; i<=n; i++) ps[i]=ps[i-1]+a[i];int nm=0;int maxf=INT_MIN;for(int i=1; i<=n; i++){nm=max(a[i],nm+a[i]);maxf=max(maxf,nm);ls[i]=maxf;}nm=0;maxf=INT_MIN;for(int i=n; i>=1; i--){nm=max(a[i],nm+a[i]);maxf=max(maxf,nm);rs[i]=maxf;}int ans=INT_MIN;for(int i=1; i<n; i++){if(i+2<=n) ans=max(ans,ls[i]+rs[i+2]);}cout<<ans;return 0;
}

#include <bits/stdc++.h>
using namespace std;
int a[1005];
int ps[1005];
int ls[1005],rs[1005];
int main()
{
    /*
    1.生成 
    2.前缀和
    3.1~n左序列（正常生成）
    4.n~1右序列（正常生成）
    5.1~n-1左右序列匹配 
    图 
    . . . . .
    ---   ---
    左    右 
    */
    int n,A,B,C;
    cin>>n>>A>>B>>C;
    for(int i=1; i<=n; i++)
    {
        ls[i]=INT_MIN;
        rs[i]=INT_MIN;
        long long tmp=((long long)A*i*i+B*i+C)%20000;
        a[i]=tmp-10000;
    }
    for(int i=1; i<=n; i++) ps[i]=ps[i-1]+a[i];
    int nm=0;
    int maxf=INT_MIN;
    for(int i=1; i<=n; i++)
    {
        nm=max(a[i],nm+a[i]);
        maxf=max(maxf,nm);
        ls[i]=maxf;
    }
    nm=0;
    maxf=INT_MIN;
    for(int i=n; i>=1; i--)
    {
        nm=max(a[i],nm+a[i]);
        maxf=max(maxf,nm);
        rs[i]=maxf;
    }
    int ans=INT_MIN;
    for(int i=1; i<n; i++)
    {
        if(i+2<=n) ans=max(ans,ls[i]+rs[i+2]);
    }
    cout<<ans;
    return 0;
}