【动态规划2】线性状态动态规划

题单链接：【动态规划2】线性状态动态规划 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

---

[P1020 NOIP1999 提高组] 导弹拦截 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=5010;
const int MAXN=1e6+10;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int a[MAXN];
int dp[MAXN];
//dp[i] 表示以i为长度时 最长不上升子序列的最后一项
//分为两种 可以直接插入在尾部 或者 插入在中间
void solve()
{
    int cnt,x;
    while(std::cin>>x)
    {
        a[++cnt]=x;
    }
    //初始化为无穷大
    memset(dp,MAXN,sizeof(dp));
    dp[1]=a[1];
    int len=1;
    for(int i=2;i<=cnt;i++)
    {
        if(a[i]<=dp[len])    dp[++len]=a[i];
        else
        {
            //最长不上升子序列是插在最后一个 注意要加上greater<int>() 因为dp数组是递减的
            //注意解引用*
            *std::upper_bound(dp+1,dp+1+len,a[i],std::greater<int>())=a[i];
        }
    }
    std::cout<<len<<"\n";

    //初始化 dp[1]=a[1]
    memset(dp,0,sizeof(dp));
    dp[1]=a[1];
    len=1;

    //Dilworth定理
    //对于一个偏序集，最少链划分等于最长反链长度
    for(int i=2;i<=cnt;i++)
    {
        if(a[i]>dp[len])    dp[++len]=a[i];     //直接插入在尾部
        //最长上升子序列是插在找到的第一个 dp数组是递增的
        else    *std::lower_bound(dp+1,dp+1+len,a[i])=a[i];     //直接插入在中间
    }
    std::cout<<len<<"\n";
}
int main(){
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

[P2285 HNOI2004] 打鼹鼠 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=5010;
const int MAXN=1e6+10;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int t[MAXN],x[MAXN],y[MAXN];
int dp[MAXN];
//dp[i] 表示到第i只鼠鼠时 机器人能够打死多少只鼠鼠
//鼠鼠出现的时间是递增的 所以按顺序枚举即可
//状态转移方程 dp[i]=dp[j]+1 if(dis[i->j]<=t[i]-t[j])
void solve()
{
    int n,m;    std::cin>>n>>m;
    for(int i=1;i<=m;i++)   std::cin>>t[i]>>x[i]>>y[i];
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        dp[i]=1;    //一开始从这个位置开始可以直接打死一只鼠鼠
        for(int j=1;j<i;j++)
        {
            if(dp[j]+1>dp[i] && std::abs(x[i]-x[j])+std::abs(y[i]-y[j])<=t[i]-t[j])
                dp[i]=dp[j]+1;
        }
        ans=std::max(ans,dp[i]);
    }
    std::cout<<ans<<"\n";
}
int main(){
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P1725 琪露诺 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=5010;
const int MAXN=2e5+10;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll a[MAXN];
std::deque<ll> dq;
ll dp[MAXN];
//dp[i]表示走到编号为i的格子时 最大冰冻之数 (因为原题中有i==0 也就是起点)
//状态转移方程 dp[j]=max(dp[i])+a[j] (i+l<=j<=i+r)
//有点像一个滑动窗口 所以我们可以使用单调队列来解决
//根据自己的理解写了一下 挂了一些细节 RE啥的 hack暂时没通过(sb洛谷 我原来的答案是错的 居然能过)
//问题 1 没有注意到初始化dp数组 导致hack点没过
//    2 要输入的n+1个点 这个已经解决了
//    3 RE的问题:其实编号为0->l-1的点是没有dp值的 所以j得从l开始 对应的j编号也要减l
//    4 dp数组更新时没有条件需求 ans要赋值为无穷小
//    5 注意看清题意 j+r>n就算到达 注意在这些范围内更新
//    6 dp[j]=-0x3f3f3f 但是bzd memset出错了
void solve()
{
    int n,l,r;  std::cin>>n>>l>>r;
    for(int i=0;i<=n;i++)   std::cin>>a[i],dp[i]=-0x3f3f3f;
    int len=r-l+1;
    dp[0]=0;
    ll ans=-0x3f3f3f;
    for(int j=l;j<=n;j++)
    {
        if(!dq.empty() && j-dq.front()>=len)    dq.pop_front();
        while(!dq.empty() && dp[dq.back()]<=dp[j-l])   dq.pop_back();
        dq.push_back(j-l);
        dp[j]=dp[dq.front()]+a[j];
        if(j+r>n)   ans=std::max(ans,dp[j]);
    }
    std::cout<<ans<<"\n";
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P4933 大师 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=2e5+10;
const int mod=998244353;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int a[1010];
ll dp[1010][N<<1];
//dp[i][d] 表示前i个塔中 高度差为d的方案数
//状态转移方程
//dp[i][h[i]-h[j]]+=dp[j][h[i]-h[j]]+1 注意取模 由于d可能为负数 所以d可以加上一个常数
//ans 就是所有可能情况的和
//方案数 是+= 不是=
//还有一个问题 就是d是+N的 所以可能太大 数组第二维度需要开成2*N
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)   std::cin>>a[i];
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            dp[i][a[i]-a[j]+N]+=dp[j][a[i]-a[j]+N]+1;
            dp[i][a[i]-a[j]+N]%=mod;
            //这里先加原来的 再取模 否则会WA
            ans+=dp[j][a[i]-a[j]+N]+1;
            ans%=mod;
        }
    }
    //不要忘记漏了一个也成立
    std::cout<<(ans+n)%mod<<"\n";
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P1439 【模板】最长公共子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=5010;
const int MAXN=1e6+10;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int a[MAXN],b[MAXN];
int dp[MAXN];
std::map<int,int> mp;
//dp[i] 表示以i为长度时 最长不上升子序列的最后一项
//分为两种 可以直接插入在尾部 或者 插入在中间
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)
    {
        std::cin>>a[i];
        mp[a[i]]=i;
    }
    for(int i=1;i<=n;i++)   std::cin>>b[i];
    dp[1]=mp[b[1]];
    int len=1;
    for(int i=2;i<=n;i++)
    {
        if(mp[b[i]]>dp[len])    dp[++len]=mp[b[i]];
        else    *(std::lower_bound(dp+1,dp+1+len,mp[b[i]]))=mp[b[i]];
    }
    std::cout<<len<<"\n";
}
int main(){
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

[P1435 IOI2000] 回文字串 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=5010;
const int MAXN=1e6+10;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int dp[1010][1010];
//一开始以为这道题可以使用nlogn的二分优化方法做 后来发现是不可行的
//以样例为例 ab3bd-->db3ba
//原来记录编号 12345->54321
//这么做 其实不可能构造出一个LIS的
//问题就在于它们之中有相同的元素 但是它们的位置标记却没有改变
//采取优化方法的前提是：序列其中的元素互不相同
//所以这道题只能使用普通方法做了
void solve()
{
    std::string s;  std::cin>>s;
    int n=s.length();
    std::string t;  t=s;
    std::reverse(t.begin(), t.end());
    t='@'+t;
    s='@'+s;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(s[i]==t[j])  dp[i][j]=dp[i-1][j-1]+1;
            else    dp[i][j]=std::max(dp[i-1][j],dp[i][j-1]);
        }
    }
    //减去它们的公共部分就是需要插入的字符数
    std::cout<<n-dp[n][n]<<"\n";
}
int main(){
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P1874 快速求和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

针对hack的一些看法：P1874 快速求和 - 洛谷专栏 (luogu.com)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
/*
int dp[45][MAXN];
int num[45][45];
std::string s;
int getNum(int l,int r)
{
    int i=l;
    while(i<=r && s[i]=='0')    i++;
    if(i>r)return 0;
    if(r-i+1>6) return INF;
    else return std::stoi(s.substr(i,r-i+1));
}
void solve()
{
    std::cin>>s;
    int n;  std::cin>>n;
    s='0'+s;
    for(int i=1;i<s.length();i++)
    {
        for(int j=i;j<s.length();j++)
        {
            num[i][j]=getNum(i,j);
        }
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=-1;
    for(int i=1;i<s.length();i++)
    {
        for(int j=0;j<=n;j++)
        {
            for(int k=1;k<=i;k++)
            {
                if(j>=num[i-k+1][i])    dp[i][j]=std::min(dp[i-k][j-num[i-k+1][i]]+1,dp[i][j]);
            }
        }
    }
    if(dp[s.length()-1][n]>=s.length()-1)   std::cout<<-1<<"\n";
    else    std::cout<<dp[s.length()-1][n]<<"\n";
}
*/
ll num[45][45];
ll dp[45][MAXN];
//dp[i][j] 表示前i个数中 和为j所需要添加的+
//num[i][j]表示从编号为i的数到编号为j的数 构成的数字
//状态转移方程 dp[i][j]=min(dp[i][j],dp[i-k+1][j-num[i-k][i]]+1)  k表示的区间的长度
//在这道题上花了很长时间了
//一个方面就是没想到num数组的更新的问题 不过后来解决了
//其实状态需转移方程不难想 问题在于预处理 这个预处理真的是毒瘤
//第一个就是 dp[0][0]的初始化 如果长度为0和为 不需要加加号就可以使和为0 但第一次算会加1 因此初始状态dp[0][0]设为-1
//dp 数组初始化 memset只能0-255 所以不要乱用memset

//也许找到了一种方法? 看看num是否超出范围 如果超出 就赋值为INF
//其实就是上面文章提供的写法
void solve2()
{
    std::string s;  std::cin>>s;
    ll n;  std::cin>>n;
    ll len=s.length();
    s='0'+s;
    for(ll i=1;i<=len;i++)
    {
        for(ll j=i;j<=len;j++)
        {
            num[i][j]=num[i][j-1]*10+s[j]-'0';
        }
    }
    for(ll i=1;i<=len;i++)
    {
        for(ll j=0;j<=n;j++)
        {
            dp[i][j]=0x3f3f3f3f;
        }
    }
    //dp[1][num[1][1]]=0;
    dp[0][0]=-1;
    for(ll i=1;i<=len;i++)
    {
        for(ll j=0;j<=n;j++)
        {
            for(ll k=0;k<i;k++)
            {
                if(j>=num[i-k][i])    dp[i][j]=std::min(dp[i][j],dp[i-k-1][j-num[i-k][i]]+1);
            }
        }
    }
    if(dp[len][n]>=len)     std::cout<<-1<<"\n";
    else    std::cout<<dp[len][n]<<"\n";
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve2();
    return 0;
}

大佬师兄指点后的代码

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll num[45][45];
ll dp[45][MAXN];
//dp[0][j]没初始化导致WA
//然后num数组因为有些值会爆long long从而可能变成负值 导致dp转移式子中会越界 导致RE
//终于解决了一个困扰已久的问题
//memset(dp,0x3f,sizeof(dp)) memset是取赋值的后八位(也就是一个字节填充全部的字节,int就是由0x3f的后8位赋值全部的字节)
//0x3f:00111111     dp->00111111 00111111 00111111 001111111
void solve2()
{
    std::string s;  std::cin>>s;
    ll n;  std::cin>>n;
    ll len=s.length();
    s='0'+s;
    for(ll i=1;i<=len;i++)
    {
        for(ll j=i;j<=len;j++)
        {
            num[i][j]=num[i][j-1]*10+s[j]-'0';
        }
    }
    memset(dp,0x6f,sizeof(dp));
    dp[0][0]=-1;
    for(ll i=1;i<=len;i++)
    {
        for(ll j=0;j<=n;j++)
        {
            for(ll k=0;k<i;k++)
            {
                if(j>=num[i-k][i] && num[i-k][i]>=0)    dp[i][j]=std::min(dp[i][j],dp[i-k-1][j-num[i-k][i]]+1);
            }
        }
    }
    if(dp[len][n]>=len)     std::cout<<-1<<"\n";
    else    std::cout<<dp[len][n]<<"\n";
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve2();
    return 0;
}

P2758 编辑距离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int dp[2010][2010];
//dp[i][j] 表示到a的第i个字符 b的第j个字符 使得a==b 的操作次数
//状态转移方程 dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+(a[i]!=b[j]))
//根据题意 初始化dp[i][0]=i,dp[0][j]=j 最基本的情况就是长度为0的情况
void solve()
{
    std::string a,b;    std::cin>>a>>b;
    a="@"+a;
    b="@"+b;
    for(int i=1;i<a.size();i++)
    {
        dp[i][0]=i;
    }
    for(int j=1;j<b.size();j++)
    {
        dp[0][j]=j;
    }
    for(int i=1;i<a.size();i++)
    {
        for(int j=1;j<b.size();j++)
        {
            dp[i][j]=std::min({dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+(a[i]!=b[j])});
        }
    }
    std::cout<<dp[a.size()-1][b.size()-1];
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

[P1091 NOIP2004 提高组] 合唱队形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int dp[110],g[110];
//思路不难想 从1->n 求一遍LIS 再从n->1 求一遍LIS 枚举位置 就可以求出来了
//dp: 1->n
//g: 1->n
//不要忘记单独一个点初始化为1
int a[110];
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)   std::cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        dp[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])   dp[i]=std::max(dp[j]+1,dp[i]);
        }
    }
    //不要使用reverse 否则编号乱了
    //std::reverse(a+1,a+1+n);
    for(int i=n;i>=1;i--)
    {
        g[i]=1;
        for(int j=n;j>i;j--)
        {
            if(a[i]>a[j])   g[i]=std::max(g[j]+1,g[i]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=std::max(ans,dp[i]+g[i]-1);		//-1 否则会把自己算重复了
    }
    std::cout<<n-ans<<"\n";
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P1854 花店橱窗布置 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
ll a[110][110];
ll dp[110][110];
/*
//dp[i][j]表示 以前i束花中 前j个花瓶中 可以获得的最大美学价值
//a[i][j]   花束i摆放在花瓶j中的美学值
//状态转移方程
//dp[i][j]=max(dp[i][j],dp[i-1][j-1],dp[i-1][j-2].....dp[i-1][i-1])
void print(ll x,ll y)
{
    if(x)
    {
        ll p=x;
        while(dp[x][p]!=y)  p++;
        print(x-1,y-a[x][p]);
        std::cout<<p<<" ";
    }
}
void solve()
{
    int f,v;    std::cin>>f>>v;
    for(int i=1;i<=f;i++)
    {
        for(int j=1;j<=v;j++)
        {
            std::cin>>a[i][j];
            dp[i][j]=-2E9;
        }
    }
    dp[0][0]=0;
    for(int i=1;i<=f;i++)
    {
        for(int j=i;j<=v;j++)
        {
            //dp[i][j]=std::max(dp[i-1][j-1]+a[i][j],dp[i][j]);
            for(int k=1;k<=j-i+1;k++)
            {
                dp[i][j]=std::max(dp[i][j],dp[i-1][j-k]+a[i][j]);
            }
        }
    }
    ll ans=0;
    for(int i=f;i<=v;i++)
    {
        ans=std::max(ans,dp[f][i]);
    }
    std::cout<<ans<<"\n";
    print(f,ans);
}
*/
//上面的方法最后一个点WA了 下面的这种方法跟我一开始想的相似 但是有些地方又不太一样
//主要是学习一下如何用记录
struct node
{
    int pos[110];       //pos数组记录答案
    int p;      //指针
}book[110][110];
void solve2()
{
    int f,v;    std::cin>>f>>v;
    memset(dp,-127,sizeof(dp));
    for(int i=1;i<=f;i++){
        for(int j=1;j<=v;j++)
        {
            std::cin>>a[i][j];
        }
    }
    for(int i=0;i<=v;i++)   dp[0][i]=0;     //最初一朵花都没插 所以是0
    for(int i=1;i<=f;i++)
    {
        for(int j=i;j<=v;j++)
        {
            if(dp[i-1][j-1]+a[i][j]>dp[i][j-1])     //这里的状态转移方程和上面不一样
            //这样理解 dp[i][j-1]表示 第i束花放在第j-1个花瓶可以获得的最大美学价值
            //原来这里可能有花并且摆法更好 也就是 dp[i-1][j-1]+a[i][j]>dp[i][j-1] 那么就要让位了
            //注意下面更新的是dp[i][j]
            {
                book[i][j]=book[i-1][j-1];  //从前一个情况继承过来
                book[i][j].pos[++book[i][j].p]=j;
                dp[i][j]=dp[i-1][j-1]+a[i][j];
            }
            else
            {
                book[i][j]=book[i][j-1];
                dp[i][j]=dp[i][j-1];
            }
        }
    }
    std::cout<<dp[f][v]<<"\n";
    for(int i=1;i<=book[f][v].p;i++)
    {
        std::cout<<book[f][v].pos[i]<<" ";
    }
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve2();
    return 0;
}

P1833 樱花 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int v[MAXN],w[MAXN],dp[MAXN];
void solve()
{
    int n,sth,stm,eth,etm,cnt=0;
    char ch;
    std::cin>>sth>>ch>>stm>>eth>>ch>>etm;
    int tot=eth*60+etm-sth*60-stm;
    std::cin>>n;
    for(int i=1;i<=n;i++)
    {
        int t,c,p;  std::cin>>t>>c>>p;
        if(p==0)    p=999;
        for(int j=1;j<=p;j<<=1)
        {
            w[++cnt]=j*t;
            v[cnt]=j*c;
            p-=j;
        }
        if(p)   w[++cnt]=p*t,v[cnt]=p*c;
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=tot;j>=w[i];j--)
        {
            dp[j]=std::max(dp[j-w[i]]+v[i],dp[j]);
        }
    }
    std::cout<<dp[tot]<<"\n";
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

[P2340 USACO03FALL] Cow Exhibition G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e6+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
//ll dp[410][410];
int s[410],f[410];
//两个限制条件的背包问题
//一开始的思路是dp[i][j] 表示情商和为i 智商和为j的 所取得的最大值
//但是发现数据范围有负数 并且是1<=n<=400 -1000<=s(f)<=1000
//为了处理这个问题数组会爆炸 所以不行
//换个思路 背包一般是求最大体积下的最大值
//那么我们可以类似设计出 最大智商和下的最大情商和
//dp[i] 表示智商和为i的情况下 可以获得的最大情商和
//为了处理负数的问题 我们可以一开始把智商都加上1000
//所以数组的范围是 400*1000*2=800000
int dp[MAXN];
int cnt[MAXN];
//状态转移方程 dp[j]=max(dp[j-s[i]]+f[i],dp[j])
//一开始想的是能否把s[i]都加上1000 再转移 但是这样需要记录路径 我自己写挂了
//所以采用题解的方法 干脆把整个数组进行偏移400 * 1000
//还需要注意一点 如果s[i]是负的 那么j-s[i]>j了 这时就得改变for的顺序 改为正序枚举
void solve2()
{
    int n;  std::cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        std::cin>>s[i]>>f[i];
    }
    memset(dp,-0x3f,sizeof(dp));
    dp[400000]=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]>=0)
        {
            for(int j=800000;j>=s[i];j--)
            {
                dp[j]=std::max(dp[j],dp[j-s[i]]+f[i]);
            }
        }
        else
        {
            //在这里时 傻乎乎的犯了一个错误 这里需要从0开始 不能从400000开始
            //因为智商是有负的 我们只是进行了偏移而已 不能不更新
            for(int j=0;j<=800000+s[i];j++)
            {
                dp[j]=std::max(dp[j],dp[j-s[i]]+f[i]);
            }
        }
    }
    int ans=0;
    for(int i=400000;i<=800000;i++)
    {
        if(dp[i]>=0)
        {
            ans=std::max(ans,dp[i]+i-400000);
        }
    }
    std::cout<<ans<<"\n";
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve2();
    return 0;
}

P4310 绝世好题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int a[MAXN];
int dp[MAXN];
int num[MAXN];
//dp[i] 表示以第i个数为结尾 能够得到的子序列b的最长长度
//状态转移方程 dp[i]=dp[j]+1  if(dp[i]<dp[j]+1 && i>j && a[i]&a[j]!=0)
// ok TLE一个点 果然还是太侥幸了 修改一下方法
// 其实可以发现 一直更新是非常耗时的 而且每次查询的区间是从1->i 1->i+1 1->i+2 长度 加一
//那么其实我们可以记录当前区间的最大值 然后再i++后 判断新的是否大于原来的dp[i]即可
//不用开数组 直接ans记录 更新即可
//其实这种方法不是正解 明天再补吧 太晚了
void solve2()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)   std::cin>>a[i],     dp[i]=1;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i-1;j>0;j--)
        {
            if(dp[i]>ans)   break;
            if(dp[i]<dp[j]+1 && (a[i]&a[j])!=0)
            {
                dp[i]=dp[j]+1;
            }
        }
        ans=std::max(ans,dp[i]);
    }
    std::cout<<ans<<"\n";
}

int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve2();
    return 0;
}

P1004 [NOIP2000 提高组] 方格取数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int dp[12][12][12][12];
//dp[i][j][k][l] 表示第一次走到(i,j) 第二次走到(k,l)可以获得的最大价值
//状态转移方程dp[i][j][k][l]
//由于只能向下或者向右走
//所以一共有四种情况
//状态转移方程
//dp[i][j][k][l]=max(dp[i-1][j][k-1][l],dp[i][j-1][k][l-1],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l])+num[i][j]+num[k][l]
//注意 走过了就num[i][j] 其数值变为0 所以需要判重
int num[12][12];
//num数组表示迷宫
void solve2()
{
    int n;  std::cin>>n;
    int a,b,c;
    while(std::cin>>a>>b>>c && (a||b||c))
    {
        num[a][b]=c;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=n;k++)
            {
                for(int l=1;l<=n;l++)
                {
                    dp[i][j][k][l]=std::max({dp[i-1][j][k-1][l],dp[i][j-1][k][l-1],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l]})+num[i][j]+num[k][l];
                    //判重
                    if(i==k && j==l)    dp[i][j][k][l]-=num[i][j];
                }
            }
        }
    }
    std::cout<<dp[n][n][n][n];
}

int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve2();
    return 0;
}

P1541 [NOIP2010 提高组] 乌龟棋 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int a[360];
int dp[45][45][45][45];
//dp[i] 表示到第i个格子可以获得的最多分数
//dp[i]=max(dp[i],dp[i-1]+a[i],dp[i-2]+a[i],dp[i-3]+a[i],dp[i-4]+a[i])
//发现这个思路是错误的 因为题目中没有将其和方格中的分数绑定在一起
//因为需要考虑牌的数目 所以不妨设dp[a][b][c][d] 依次表示第一种牌 第二种牌 第三第四
//通过枚举牌的数量 可以进行状态转移
int mp[6];
void solve3()
{
    int n,m;    std::cin>>n>>m;
    for(int i=1;i<=n;i++)   std::cin>>a[i];
    for(int i=1;i<=m;i++)
    {
        int x;  std::cin>>x;
        mp[x]++;
    }
    //注意一开始的分数就是a[1]
    dp[0][0][0][0]=a[1];
    //for(int i=1;i<=4;i++)   std::cout<<mp[i]<<" ";
    //std::cout<<"\n";
    for(int i=0;i<=mp[1];i++)
    {
        for(int j=0;j<=mp[2];j++)
        {
            for(int k=0;k<=mp[3];k++)
            {
                for(int l=0;l<=mp[4];l++)
                {
                    auto &d=dp[i][j][k][l];
                    //这里要特别注意加1 因为是从1开始的 要算上1这个开始的格子
                    int dis=1*i+2*j+3*k+4*l+1;
                    if(i)   d=std::max(d,dp[i-1][j][k][l]+a[dis]);
                    if(j)   d=std::max(d,dp[i][j-1][k][l]+a[dis]);
                    if(k)   d=std::max(d,dp[i][j][k-1][l]+a[dis]);
                    if(l)   d=std::max(d,dp[i][j][k][l-1]+a[dis]);
                }
            }
        }
    }
    std::cout<<dp[mp[1]][mp[2]][mp[3]][mp[4]];

}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve3();
    return 0;
}

P3147 [USACO16OPEN] 262144 P - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题解链接：题解 P3147 【[USACO16OPEN]262144】

#include<bits/stdc++.h>
using ll=long long;
const int N=2e4+10;
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const int MAX=270007;
typedef std::pair<int,int> pii;
typedef std::pair<double,int> pdi;
int dp[61][MAX];
//真难 这个dp真想不出来
//直接看题解吧
void solve3()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;  std::cin>>x;
        dp[x][i]=i+1;
    }
    int ans=0;
    for(int i=2;i<=58;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(dp[i][j]==0)
            {
                dp[i][j]=dp[i-1][dp[i-1][j]];
            }
            if(dp[i][j])    ans=i;
        }
    }
    std::cout<<ans<<"\n";
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(nullptr);
    int t=1;
    //std::cin>>t;
    while(t--)solve3();
    return 0;
}

P2679 [NOIP2015 提高组] 子串 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)