题目描述

狗子喜欢一个序列 a，当且仅当

∀i,a i ​ ×a i+1 ​ ≤k(a i ​ +a i+1 ​ )。

你需要求出最长的子序列满足以上条件。

输入格式

第一行两个整数

n,k。

接下来一行

n 个整数

A 1 ​ ,A 2 ​ ,⋯,A n ​ 表示序列。

输出格式

第一行一个整数

x 表示答案。

第二行

x 个整数表示一个合法的子序列。

注意即使你不会求子序列，你也需要在第二行输出

x 个整数以拿到输出

x 的部分分。

输入数据 1 10 2 1 2 3 4 7 1 6 1 3 65535 输出数据 1 8 1 2 3 4 1 6 1 65535

代码：

#include<bits/stdc++.h>
using namespace std; 
int n,k,a[2005],v[2005],ans=-1; 
long long sum1,sum2; 
void dfs(int step,int cnt) {
    if(step==n+1) {
        ans=max(ans,cnt); 
        return; 
    }
    sum1=1ll*a[step]*a[step-1]; 
    sum2=1ll*k*(a[step]+a[step-1]); 
    if(sum1>sum2) {dfs(step+1,cnt); return; }
    v[cnt+1]=a[step]; 
    dfs(step+1,cnt+1);  
}
int main()
{
    //freopen("seq.in","r",stdin); 
   	//freopen("seq.out","w",stdout); 

    cin.tie(0); cout.tie(0); 
    cin>>n>>k; 
    for(int i=1;i<=n;i++) cin>>a[i]; 
    dfs(1,0); cout<<ans<<"\n";
    for(int i=1;i<=ans;i++) cout<<v[i]<<" ";  

    return 0; 
}

(k=2时0分)