CF1262D1 Optimal Subsequences (Easy Version)


题意简述:

给定一个长度为$n$的序列 给定$m$次询问$k$和$pos$表示:长度为$k$的总值和最大的子序列里的第$pos$位的值是几(假如有多个子序列满足要求字典序最小的一个)

题解:

这道题我比赛时候做了easy版 所以还是想糊一下easy的版本 总值最大的子序列 看着就很dp 看着就很背包
我们可以设$f[i][j]$表示当前考虑到第$i$位且子序列长度为$j$的最大价值
那么就有转移方程:$f[i][j]=max(f[i-1][j],f[i-1][j-1]+a[i])$
在做了一遍dp以后我们就可以去求方案 但注意要求是字典序最小 所以假如我们正着dp后面方案就要倒着来 这样字典序就不一定最小了 所以我们需要倒着dp然后正着求方案 然后把方案存下来 最后直接查询即可(当然我这里就直接每次现求方案了)

AC代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define ll long long
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define mst(a,b) memset((a),(b),sizeof(a))
#define PII pair<int,int>
using namespace std;
template<class T>inline void read(T &x) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
}
const int inf=0x3f3f3f3f;
const int maxn=150;
int n,m;
ll a[maxn];
ll f[maxn][maxn],pre[maxn][maxn];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=n;i>=1;i--) f[i][1]=max(a[i],f[i+1][1]);
    for(int i=n;i>=1;i--)
    {
        for(int len=1;len<=n-i+1;len++)
        {
            if(len<n-i+1) f[i][len]=f[i+1][len];
            if(f[i+1][len-1]+a[i]>f[i][len])
            {
                f[i][len]=f[i+1][len-1]+a[i];
            }

        }
    }
    cin>>m;
    while(m--)
    {
        int k,pos;
        cin>>k>>pos;
        int temp=k,tot=0;
        for(int i=1;i<=n;i++)
        {
            if(f[i][temp]==f[i+1][temp-1]+a[i])
            {
                temp-=1;
                tot++;
                if(tot==pos)
                {
                    cout<<a[i]<<endl;
                    break;
                }
            }
        }
    }
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
CF1255C League of Leesins CF1255C League of Leesins
题意简述:给定一个长度为$n$的排列 并将连续的三个作为一组 如$[1,2,3,4,5]$就有三组$[1,2,3],[2,3,4],[2,4,5]$现在我们可以把每组内的数顺序交换 也可以把组交换 现在给出$n-2$个经过交换后的组 让你求
2019-11-26
下一篇 
CF1262D2 Optimal Subsequences (Hard Version) CF1262D2 Optimal Subsequences (Hard Version)
题意简述:给定一个长度为$n$的序列 给定$m$次询问$k$和$pos$表示:长度为$k$的总值和最大的子序列里的第$pos$位的值是几(假如有多个子序列满足要求字典序最小的一个) 题解:这道题的hard其实就和dp没啥关系 因为我们发现
2019-11-25
  目录