给定一个长度为$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然后正着求方案 然后把方案存下来 最后直接查询即可（当然我这里就直接每次现求方案了）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#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;
}
|