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

最新推荐文章于 2025-01-02 14:54:26 发布

小衣同学

最新推荐文章于 2025-01-02 14:54:26 发布

阅读量414

点赞数

分类专栏： # 基础dp(线性dp/计数dp/递推dp/子序列dp) 文章标签：算法动态规划线性dp c++

本文链接：https://blog.csdn.net/Code92007/article/details/129906240

版权

基础dp(线性dp/计数dp/递推dp/子序列dp) 专栏收录该内容

86 篇文章

订阅专栏

文章介绍了一个关于数组处理的问题，其中涉及到对长度为n的数组进行多次删除操作，目标是使剩余元素之和等于特定值x。使用动态规划的方法，通过状态转移方程dp[i][j][k]来记录考虑前i个元素时，元素和为j且第i个元素是否被删的情况。最后，对于每个x，给出最小删除次数或者输出-1表示无法实现。文章提供了一个C++代码示例来解决这个问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

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