P9468

Amoribus · 2025-05-14 15:37:33 · 题解

可以用 dp 做。

设 dp_{i,j,k} 表示前 i 个数选 j 个进行填充，花 k 步能达到的最大值。

状态是 O(n^4) 的（转移步数会达到 O(n^2) 量级），可以通过 n\leq 100 的数据。

在一个决策点上，你有两种选择：

• 你要把 a_i 换到 [1,j] 的区间里，此时换到 a_j 是最优的。dp_{i-1,j-1,k-i+j}+a_i \to dp_{i,j,k}。
• 不动 a_i。dp_{i-1,j,k}\to dp_{i,j,k}。

最后的答案是 \min \limits_{dp_{n,f,k}\geq t}k。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=1e16;
int dp[109][109][5009];
int N,F,T,ans=inf,presum=0;
int a[109];
signed main()
{
    cin>>N>>F>>T;
    for(int i=1;i<=N;i++) cin>>a[i];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=min(i,F);j++){
            for(int k=0;k<=i*(i-1)/2;k++){
                dp[i][j][k]=dp[i-1][j][k];
                if(k-i+j>=0)
                dp[i][j][k]=max(dp[i-1][j-1][k-i+j]+a[i],dp[i][j][k]);
            }
        }
    }
    for(int k=0;k<=N*(N-1)/2;k++){
        if(dp[N][F][k]>=T) ans=min(ans,k);
    }
    if(ans==inf) cout<<"NO";
    else cout<<ans<<endl;
    return 0;
}