Atcoder DP Contest

这里是题单的链接：AtCoder DP Contest - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

目前还有些题目没写 后续学完相关知识再补

A

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=1e6+10;
const int mod=1e9+7;
const double PI=acos(-1);
int h[MAXN];
ll dp[MAXN];
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)   std::cin>>h[i];
    //dp[1]=h[1],不需要初始化dp[1]，本身就是0
    dp[2]=abs(h[2]-h[1]);
    for(int i=3;i<=n;i++)
    {
        dp[i]=std::min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
    }
    std::cout<<dp[n]<<"\n";
}
int main() {
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

B

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=1e6+10;
const int mod=1e9+7;
const double PI=acos(-1);
int h[MAXN];
ll dp[MAXN];
//dp[i]记作跳到第i块石头所花费的最小体力
//状态转移方程：
//dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]) dp[i-2]+abs(h[i]-h[i-2])------)
void solve()
{
    int n;  std::cin>>n;
    int k;  std::cin>>k;
    for(int i=1;i<=n;i++)   std::cin>>h[i],dp[i]=1e15;
    dp[1]=0;
    //dp[2]=abs(h[2]-h[1]);
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=std::min(k,i-1);j++)
        dp[i]=std::min(dp[i-j]+abs(h[i]-h[i-j]),dp[i]);
    }
    std::cout<<dp[n]<<"\n";
}
int main() {
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

C

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
int a[MAXN],b[MAXN],c[MAXN];
ll dp[MAXN][5];
//dp[i][j]表示第i天，以第j种活动结束
//状态转移方程
//假设j=1
// 1-a 2-b 3-c
//dp[i][1]=max(dp[i-1][2]+a[i],dp[i-1][3]+a[i])
//其他的同理
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)std::cin>>a[i]>>b[i]>>c[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=3;j++)
        {
            if(j==1)dp[i][j]=std::max(dp[i-1][j+1]+a[i],dp[i-1][j+2]+a[i]);
            if(j==2)dp[i][j]=std::max(dp[i-1][j-1]+b[i],dp[i-1][j+1]+b[i]);
            if(j==3)dp[i][j]=std::max(dp[i-1][j-1]+c[i],dp[i-1][j-2]+c[i]);
        }
    }
    std::cout<<std::max({dp[n][1],dp[n][2],dp[n][3]})<<"\n";
}
int main() {
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

D

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
int w[MAXN], v[MAXN];
ll dp[MAXN];
//最初的想法是三个维度：容量，取到了第i个物品，以及是否取
//是否取对后面的状态转移没有任何影响，所以可以删去
//取到第i个物品的状态转移似乎也没有影响，所以可以删去
//保留容量维度
//dp[i]表示容量为i时，最大价值
void solve()
{
    int n;  std::cin>>n;
    int W;  std::cin>>W;
    for(int i=1;i<=n;i++)   std::cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=W;j>=w[i];j--)	//注意要倒序枚举 否则是从更新后的状态转移过来的
            dp[j]=std::max(dp[j],dp[j-w[i]]+v[i]);
    }
    std::cout<<dp[W]<<"\n";
}
int main() {
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

E

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=1e6+10;
const int mod=1e9+7;
const double PI=acos(-1);
int w[MAXN], v[MAXN];
int dp[MAXN];
//一道很有趣的题目
//这道题的范围很大 看了一眼题解区 以为题目修改过 或者 翻译有误
//仔细一想 这道题是从一个新奇的角度分析背包问题
//注意到范围是1e9 即使是一维也无法解决
//要求的还是同样的问题 从另外一个角度入手
//仍然是一维
//dp[i] 表示的是总价值为i时 最小的体积 有点倒反天罡的趣味
//这里取最小值 是因为体积越小 越能容纳更多的物品 总价值也就越大 这是一种贪心的想法
//状态转移方程
//dp[i]=min(dp[i],dp[i-v[j]]+w[i])
void solve()
{
    int n;  std::cin>>n;
    int W;  std::cin>>W;
    int V=0;
    for(int i=1;i<=n;i++)   std::cin>>w[i]>>v[i],V+=v[i];
    
    //不要忘记初始化
    for(int i=1;i<=V;i++)
    {
        dp[i]=0x3f3f3f3f;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=v[i];j--)
            dp[j]=std::min(dp[j],dp[j-v[i]]+w[i]);
    }
    
    for(int i=V;i>=0;i--)
    {
        if(dp[i]<=W)
        {
            std::cout<<i<<'\n';
            return;
        }
    }
}
int main() {
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

F

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=1e6+10;
const int mod=1e9+7;
const double PI=acos(-1);
int dp[3010][3010];
//dp[i][j]表示以s[i] t[j]结尾的最长公共子序列长度
//状态转移方程：dp[i][j]=dp[i-1][j-1]+1 if s[i]==t[j] else max(dp[i-1][j],dp[i][j-1])
//这里注意需要先把字符串加上@，这样才避免预处理时候的麻烦
void solve()
{
    std::string s,t;    std::cin>>s>>t;
    int n=s.length(),m=t.length();
    std::string ans="";
    s="@"+s,t="@"+t;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;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]);
            }
        }
    }
    //使用双指针实现
    //如果是正序 无法保证一定是最长的 需要倒序(因为已经知道了最长的长度，可以保证一定是最优的)
    int sp=n,tp=m;
    while(sp>0&&tp>0)
    {
        if(s[sp]==t[tp])
        {
            ans+=s[sp];
            sp--;tp--;
        }
        else
        {
            if(dp[sp-1][tp]>dp[sp][tp-1])   sp--;
            else tp--;
        }
    }
    std::reverse(ans.begin(),ans.end());
    std::cout<<ans<<"\n";
}
int main() {
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

G

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=1e6+10;
const int mod=1e9+7;
const double PI=acos(-1);
int dp[MAXN],in[MAXN];
//dp[i] 表示到第i个节点的最长路径
//状态转移方称 dp[i]=max(dp[j]+1,dp[i]); j为i的父节点
struct Edge{
    int from,to;
};
std::vector<Edge> edge[MAXN];
void add(int from,int to)
{
    Edge e={from,to};
    edge[from].push_back(e);
}
int b[MAXN];
//记得搜索的顺序和dp是相反的
//dp是由起点->终点 而dfs是从终点->起点
int dfs(int x)
{
    /*
    for(auto t:edge[x])
    {
        if(dp[t.to]<dp[t.from]+1)
        {
            dp[t.to]=dp[t.from]+1;
        }
        dfs(t.to);
    }
     */
    //这里写挂了，导致重复dfs了很多次


    //新问题
    //这里需要判断一下dp[x]是否为0 否则搜索太多次 也会TLE
    if(dp[x]==0) {
        for (auto t: edge[x]) {
            dp[x] = std::max(dfs(t.to) + 1, dp[x]);
        }
    }
    return dp[x];
}
void solve()
{
    int n,m;    std::cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        std::cin>>u>>v;
        add(u,v);
        //in[v]++;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=std::max(dfs(i),ans);
    }
    std::cout<<ans<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

H

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=1e6+10;
const int mod=1e9+7;
const double PI=acos(-1);
int dp[1010][1010];
char mp[1010][1010];
void solve()
{
    int h,w;    std::cin>>h>>w;
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)std::cin>>mp[i][j];
    }
    for(int i=1;i<=h;i++)
    {
        if(mp[i][1]=='#')break;
        else dp[i][1]=1;
    }
    for(int i=1;i<=w;i++)
    {
        if(mp[1][i]=='#')break;
        else dp[1][i]=1;
    }
    for(int i=2;i<=h;i++)
    {
        for(int j=2;j<=w;j++)
        {
            if(mp[i][j-1]!='#'&&mp[i-1][j]!='#')dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
            else if(mp[i][j-1]=='#'&&mp[i-1][j]!='#')dp[i][j]=dp[i-1][j]%mod;
            else if(mp[i-1][j]=='#'&&mp[i][j-1]!='#')dp[i][j]=dp[i][j-1]%mod;
        }
    }
    std::cout<<dp[h][w]<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

I

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=1e6+10;
const int mod=1e9+7;
const double PI=acos(-1);
double dp[3010][3010];
double p[3010];
//dp[i][j] 表示前i枚硬币中 有j枚正面朝上的概率
//状态转移方程 dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i]);
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)
    {
        std::cin>>p[i];
    }
    //dp[0][0]初始化 其他非法状态不考虑
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=dp[i-1][0]*(1-p[i]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i]);
        }
    }
    double ans=0;
    //题目要求的是正>负 看清楚题目
    for(int i=n;i+i>n;i--)
    {
        ans+=dp[n][i];
    }
    //注意输出保留10位精度
    std::cout<<std::fixed<<std::setprecision(10)<<ans<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

J

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=1e6+10;
const int mod=1e9+7;
const double PI=acos(-1);
double dp[310][310][310];
std::map<int,int> m;
//dp[i][j][k] 表示共有i个盘子中有1个寿司 j个盘子中有2个寿司 k个盘子中有3个寿司
//状态转移方程 dp[i][j][k]=n/(i+j+k)+i/(i+j+k)*dp[i-1][j][k]+j/(i+j+k)*dp[i+1][j-1][k]
//+k/(i+j+k)*dp[i][j+1][k-1]
void solve()
{
    int n;  std::cin>>n;
    int all=0;
    for(int i=1;i<=n;i++)
    {
        int x;  std::cin>>x;
        m[x]++;
    }

    //这里需要注意以下枚举的顺序
    //先枚举有3个寿司的盘子 再枚举有2个寿司的盘子 再枚举有一个寿司的盘子
    //因为寿司多的盘子 其寿司数目会减少 影响寿司少的盘子的情况
    //如果是1->2->3的顺序枚举 有一些更新的状态就没有参与到dp中了
    for(int k=0;k<=n;k++)
    {
        for(int j=0;j<=n;j++)
        {
            for(int i=0;i<=n;i++)
            {
                if(i||j||k)
                {
                    dp[i][j][k]=(double)n/(i+j+k);
                    if(i)dp[i][j][k]+=i*dp[i-1][j][k]/(i+j+k);
                    if(j)dp[i][j][k]+=j*dp[i+1][j-1][k]/(i+j+k);
                    if(k)dp[i][j][k]+=k*dp[i][j+1][k-1]/(i+j+k);
                }
            }
        }
    }

    //全部盘子都收集完了
    std::cout<<std::fixed<<std::setprecision(10)<<dp[m[1]][m[2]][m[3]]<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

K

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=1e6+10;
const int mod=1e9+7;
const double PI=acos(-1);
int a[MAXN];
int dp[MAXN];
//属于博弈论的dp
//dp[i] 表示到第i个石子的时候 当前者的胜负
//当i==0 f[0]=0;
//顺序推导 求出f[n]即可判断胜负
//认识到一个点 如果当前是必败态 那么它必然是从必胜态转移过来的
//状态转移方程
//dp[i]+=!dp[i-a[j]] 注意这里是|或者+运算 因为可能是从多个状态转移过来的 只要有一种胜利即可

//很有Nim博弈的味道 DAG推导
void solve()
{
    int n,k;    std::cin>>n>>k;
    for(int i=1;i<=n;i++)   std::cin>>a[i];
    for(int i=1;i<=k;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i>=a[j])
            {
                dp[i]|=!dp[i-a[j]];
            }
        }
    }
    std::cout<<(dp[k]?"First":"Second")<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

L

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=1e6+10;
const int mod=1e9+7;
const double PI=acos(-1);
int a[3010];
ll dp[3010][3010],sum[3010];
//这道题目有合并的性质 所以我们可以考虑使用区间dp
//dp[i][j]表示 从i到j区间内 first的最大分数
//由于这是一道博弈论问题 所以需要从对手的状态转移过来
//状态转移方程
//dp[i][j]=max(sum[i+1][j]-dp[i+1][j]+a[i],sum[i][j-1]-dp[i][j-1]+a[j])
//sum[i][j] 表示从i到j之间的区间和
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)
    {
        std::cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        dp[i][i]=a[i];
    }
    for(int i=n-1;i>=1;i--)
    {
        for(int j=i+1;j<=n;j++)
        {
            dp[i][j]=std::max(sum[j]-sum[i]-dp[i+1][j]+a[i],sum[j-1]-sum[i-1]-dp[i][j-1]+a[j]);
        }
    }
    std::cout<<-(sum[n]-2*dp[1][n]);
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

M

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
int a[110];
ll dp[MAXN],sum[MAXN];
//dp[i]表示前i颗糖分完的方案数
//dp[i]+=dp[i-(1,2,---a[j])]
//sum[i]是dp[i] dp[i-1] dp[i-2]-----的前缀和 否则会TLE
//所以就优化为dp[i]=sum[i]-sum[i-a[j]-1]
//需要注意的是i可能<=a[j] 所以dp[i]=sum[i]了 注意分类讨论

//其实直接比较好想的是dp[i][j] 表示前i个人分了j个糖果的情况 但是自己当时脑回路清奇 直接把第一维压缩了
void solve()
{
    int n,k;  std::cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        std::cin>>a[i];
    }
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        sum[0]=dp[0];
        for(int j=1;j<=k;j++)
        {
            sum[j]=(sum[j-1]+dp[j])%mod;
        }
        for(int j=0;j<=k;j++)
        {
            if(j>a[i])dp[j]=(sum[j]-sum[j-a[i]-1]+mod)%mod;
            else dp[j]=sum[j]%mod;
        }
    }
    std::cout<<dp[k]%mod<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

N

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=1e6+10;
const int mod=1e9+7;
const double PI=acos(-1);
int a[4010];
ll dp[4010][4010],sum[4010];
//一道经典的区间dp题目
//dp[i][j]表示合并成区间[i,j]所需要的最大代价
//状态转移方程
//[i,j]可以由[i,k],[k,j]合并得到 所以需要枚举k
//除了本身的代价外 还有[i,j]的区间和
//dp[i][j]=max(dp[i][k]+dp[k][j]+sum[j]-sum[i-1],dp[i][j])
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            dp[i][j]=LONG_LONG_MAX>>1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        std::cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        dp[i][i]=0;
    }
    //区间dp三个步骤
    //枚举长度
    //枚举起点
    //枚举分段点
    for(int l=2;l<=n;l++)
    {
        for(int i=1;i+l-1<=n;i++)
        {
            int j=i+l-1;
            //注意枚举的分段点是从i开始 但是要小于j,否则有可能k+1>j越界
            //原来一开始是写k=i+1 但是实际上可以是由一个数加上一个区间的合并
            for(int k=i;k<j;k++)
            {
                dp[i][j]=std::min(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1],dp[i][j]);
            }
        }
    }
    std::cout<<dp[1][n]<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

O

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=3e6+10;
const int mod=1e9+7;
const double PI=acos(-1);
//ll dp[25][MAXN];
int a[25][25];
//一道状态压缩dp 涉及到二分图匹配
//为什么会用到状压呢? 这是个二分图匹配问题 涉及集合 所以可能想到用状压 另一方面就是n比较小
//dp[i][j]表示前i个男生 到由若干个女生构成的集合j中 一一匹配的方案数
//状态转移方程 dp[i][j]=dp[i][j]+dp[i-1][j-k]  (j-k)表示j中去掉元素k
//状压dp一般下标从0开始 方便位运算(这里就是a[i][j]中i j下标从0开始)
//遇到一个奇怪的问题 第二维度开太小了 应该是RE才对 结果却是WA
//猜测越位哪些被忽略了 从而导致答案错误

int dp[MAXN];
//考虑优化 第一维可以省略
//优化后 dp[i]=dp[i]+dp[i-k] 含义一样
/*
void solve1()
{
    int n;  std::cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            std::cin>>a[i][j];
        }
    }
    dp[0][0]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<(1<<n);j++)
        {
            if(__builtin_popcount(j)==i)
            {
                for(int k=0;k<n;k++)
                {
                    if(a[i][k]&&(j&(1<<k))==0)
                    {
                        dp[i+1][j|(1<<k)]=(dp[i][j]+dp[i+1][j|(1<<k)])%mod;
                    }
                }
            }
        }
    }
    std::cout<<dp[n][(1<<n)-1]<<"\n";
}
 */
void solve()
{
    int n;  std::cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            std::cin>>a[i][j];
        }
    }
    dp[0]=1;
    for(int i=0;i<(1<<n);i++)
    {
        int cnt=__builtin_popcount(i);
        //原来是__builtin_popcount(j)==i 枚举i 看i与j是否完全配对
        for(int j=0;j<n;j++)
        {
            if(a[cnt][j]&&(i&(1<<j))==0)
            {
                dp[i|(1<<j)]=(dp[i|(1<<j)]+dp[i])%mod;
            }
        }
    }
    std::cout<<dp[(1<<n)-1]<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

P

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
struct Edge
{
    int from,to;
};
std::vector<Edge> edge[MAXN];
void add(int from,int to)
{
    Edge e={from,to};
    edge[from].push_back(e);
}
ll dp[MAXN][2];
//vis 其实跟记忆化搜索差不多
bool vis[MAXN];
//dp[i][0] 表示以第i号节点为根节点且第i号节点为白色时的方案数
//dp[i][1] 表示以第i号节点为根节点且第i号节点为黑色时的方案数
//dp[i][0]*=dp[j][0]+dp[j][1] 其中j指的是i的子节点
//dp[i][1]*=dp[j][0]
void dfs(int x)
{
    for(auto e:edge[x])
    {
        int y=e.to;
        if(vis[y])continue;
        //注意的先vis标记 否则有些情况会重复计算
        vis[y]=true;
        dfs(y);
        dp[x][0]*=(dp[y][0]+dp[y][1]);
        dp[x][0]%=mod;
        dp[x][1]*=dp[y][0];
        dp[x][1]%=mod;
    }
}
void solve()
{

    int n;  std::cin>>n;
    //没有确定根节点 所以建立双向边 首先遍历到的就是父节点
    for(int i=1;i<n;i++)
    {
        int u,v;    std::cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=dp[i][1]=1;
    }
    //这样 我们就可以默认1为根节点 直接dfs即可
    vis[1]=true;
    dfs(1);
    ll ans=0;
    ans=(dp[1][0]+dp[1][1])%mod;
    std::cout<<ans<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

Q

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=2e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
ll dp[MAXN];
ll be[1010];   //表示区间i的最大值
ll b[MAXN];    //单个元素dp[i]的max
//dp[i] 表示以第i个元素为结尾 可以得到的最大权值
//dp[i]=max(dp[j])+a[i] (1<h[j]<h[i])
//由于区间范围较大 所以需要优化一下 这里用分块
//因为是从1开始 所以前面直接枚举块 后面枚举零散的元素即可
//更新的时候 因为是单点更新 所以对应的点更新(记作A) 块也要更新(后面的元素寻找max时 A是在块中)
//总结一点 点要更新 所在的块也要更新
int h[MAXN],a[MAXN];
int block;  //块长
void update(ll x,ll y)
{
    b[x]=std::max(b[x],y);
    be[x/block+1]=std::max(be[x/block+1],y);
}
ll query(int r)
{
    ll ans=0;
    for(int i=1;i<=r/block;i++)
    {
        ans=std::max(ans,be[i]);
    }
    for(int i=r/block*block;i<=r;i++)
    {
        ans=std::max(ans,b[i]);
    }
    return ans;
}
void solve()
{
    int n;  std::cin>>n;
    block=std::sqrt(n);
    for(int i=1;i<=n;i++)
    {
        std::cin>>h[i];
    }
    for(int i=1;i<=n;i++)
    {
        std::cin>>a[i];
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        dp[i]=query(h[i]-1)+a[i];
        update(h[i],dp[i]);
        ans=std::max(ans,dp[i]);
    }
    std::cout<<ans<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

R

没写

S

#include<bits/stdc++.h>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
int a[10010],dp[10010][110][2];
//dp[pos][sum][limit][lead]
//pos limit lead 含义不变
//sum 表示到当前位时的各位数字之和

//原来一开始MLE了 最先优化 考虑删除掉 lead维度 但是还是有2个点WA了
//应该是出现了负数 最后结果加上mod 再取模即可

//还可以再进一步优化
//dp[pos][sum][limit]
//pos limit 含义不变
//sum 表示到当前位时的各位数字之和 
//考虑到D的范围是从0-100 所以其实sum的范围最大到100多即可 这里110
int cnt,D;
int dfs(int pos,int sum,bool limit)
{
    auto &d=dp[pos][sum][limit];
    int ans=0;
    if(pos==cnt)
    {
        if(sum%D==0)    return 1;
        return 0;
    }
    if(d!=-1)   return d;
    for(int i=0;i<=(limit?a[pos]:9);i++)
    {
        ans+=dfs(pos+1,(sum+i)%D,limit && i==a[pos]);
        ans%=mod;
    }
    d=ans;
    return ans;
}
void solve()
{
    std::string k;
    std::cin>>k>>D;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<k.length();i++)
    {
        a[cnt++]=k[i]-'0';
    }
    //for(int i=0;i<cnt;i++)  std::cout<<a[i];
    std::cout<<(dfs(0,0,true)-1+mod)%mod<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

T

没写

U

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
ll a[20][20];
ll dp[MAXN];
//这是一道状压dp问题
//怎么看出来 1 n范围小 2 涉及到集合处理的问题
//但我对状压还是不太熟悉 所以还是看题解了 关键还是怎么枚举集合 进行位运算
//不难想到状态转移方为 dp[i]=max(dp[i],dp[j]+dp[k])   这里的i j k就表示集合
//j 和 k 是i的子集 其实有点像之前的二分图dp 感觉处理方式都是一样的 分成不同的集合来进行处理
// 难点是进行位运算
void solve()
{
    int n;  std::cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            std::cin>>a[i][j];
        }
    }
    // 预处理
    // i枚举集合
    for(int i=0;i<(1<<n);i++)
    {
        //枚举 存在两边的元素
        for(int j=0;j<n;j++)
        {
            for(int k=j+1;k<n;k++)
            {
                //判断是否存在连边
                if((i>>j)&1 && (i>>k)&1)    dp[i]+=a[j][k];
            }
        }
    }

    //父集合
    for(int i=0;i<(1<<n);i++)
    {
        //枚举子集和
        //j=(j-1)&i 这样可以保证j是越来越小的 且是i的子集
        for(int j=i;j;j=(j-1)&i)
        {
            dp[i]=std::max(dp[i],dp[j]+dp[i^j]);
        }
    }
    std::cout<<dp[(1<<n)-1]<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

V

没写

W

没写

X

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const double PI=acos(-1);
struct node
{
    ll w,s,v;
    bool operator<(const node&b)
    {
        return w+s<b.w+b.s;
    }
}a[1010];
ll dp[MAXN];
//01背包 + 贪心
//对背包有了新的理解 限重可以抽象为当前背包的某个限制条件
//一开始在考虑怎么处理 限重的问题
//采用的是贪心的思路 如果两个货物i j 在题它们上面 想要堆叠更多的物品 不难想到 si-wj<sj-wi
//这样可以保证可以堆叠更多的物品 转换得到 si+wi<sj+wj
//那么可以这样处理
//原本的dp[i][j]方程表示的是 dp[i][j]表示前i个物品中 s+w为j时能得到的最大价值
//考虑优化 那么i维度就可以删去 --> dp[j]
//状态转移方程基本一致 dp[j]=max(dp[j],dp[j-a[i].s]+a[i].v) 注意倒序枚举
//还需要注意j 不是枚举最大的MAX 而是当前箱子的w+s 并不是一开始能够容纳的上限就是最大的 而是所枚举的箱子的MAX
//之前的背包的上限是一个固定值 是唯一且确定的 但这个不是 根据箱子的枚举而改变MAX
void solve()
{
    int n;  std::cin>>n;
    for(int i=1;i<=n;i++)   std::cin>>a[i].w>>a[i].s>>a[i].v;
    std::sort(a+1,a+1+n);
    //memset(dp,-0x3f3f3f3f,sizeof(dp));
    dp[0]=0;
    ll MAX=a[n].s+a[n].w;
    for(int i=1;i<=n;i++)
    {
        for(ll j=a[i].w+a[i].s;j>=a[i].w;j--)
        {
            dp[j]=std::max(dp[j-a[i].w]+a[i].v,dp[j]);
        }
    }
    ll ans=0;
    //补充一点 这里还需要取max
    //原本的普通背包是不用的
    //这里wsm需要? 
    for(int i=0;i<=MAX;i++)
    {
        ans=std::max(ans,dp[i]);
    }
    std::cout<<ans<<"\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    int t=1;
    //std::cin>>t;
    while(t--)solve();
    return 0;
}

Y

没写

Z

没写