[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;
}