题目
给一个长度为n(n<=3e3)的数组a(1<=ai<=3e3),
你可以进行以下操作任意次:
1. 选择一个a的连续子数组,将其删掉
对于x=1,2,...,m,分别回答问题:
1. 找到最小的删除次数,使得剩余没被删的元素之和等于x,输出最小删除次数
2. 如果不能实现,输出-1
特别地,空数组元素和,认为是0
思路来源
蔡老师
题解
dp[i][j][k]表示:考虑前i个元素时,当前没被删的元素和为j,
最后的元素(第i个元素)是否被删(0/1)时,对应的最小删除次数为dp[i][j][k],
若dp[i][j][k]为INF,则表示此状态不合法
转移则类似背包,枚举最后一个元素是删了还是没删,上一个元素是删了还是没删,
当前的01从上一次的01转移而来,四种情况
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e3+5,INF=0x3f3f3f3f;
int n,m,dp[N][N][2],a[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>a[i];
}
memset(dp,INF,sizeof dp);
dp[0][0][0]=0;
dp[0][0][1]=1;
for(int i=1;i<=n;++i){
for(int j=0;j<=m;++j){
dp[i][j][1]=min(dp[i-1][j][1],dp[i-1][j][0]+1);
if(j>=a[i])dp[i][j][0]=min(dp[i-1][j-a[i]][1],dp[i-1][j-a[i]][0]);
}
}
for(int i=1;i<=m;++i){
int ans=min(dp[n][i][0],dp[n][i][1]);
printf("%d\n",ans==INF?-1:ans);
}
return 0;
}