AtCoder Beginner Contest 275 F. Erase Subarrays(线性dp)

时间:2020-12-26 01:18:02

题目

给一个长度为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;
}