P9468

可以用 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

。

CPP

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

文章操作

相关推荐

评论

P9468