[EGOI 2023] Candy / 糖果

思路

$N$ 这么小基本就是瞎打的 DP 了。

设 $d{p}_{i,j}$ 为操作 $j$ 次后前 $i$ 项的和最大是多少。

考虑转移，我们可以枚举 $i$ 并考虑将其移动到 $p$ 位置，总共操作 $k$ 次，那么就有 $d{p}_{p,k}=\min (d{p}_{p,k},d{p}_{p-1,k-(i-p)}+a_i)$，注意转移顺序即可，时间复杂度 $O(N^{3}F)$。

代码

非常简洁的代码。

#include<bits/stdc++.h>
using namespace std;
long long n,f,t,a[105];
long long dp[105][10005];
int main()
{cin>>n>>f>>t;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)for(int p=f;p>=1;p--)//从大到小枚举符合拓扑序for(int k=i-p;k<=n*n;k++)dp[p][k]=max(dp[p][k],dp[p-1][k-(i-p)]+a[i]);for(int i=0;i<=n*n;i++)if(dp[f][i]>=t){cout<<i;return 0;}cout<<"NO";return 0;
}