网站建设科技公司外部环境分析/全媒体运营师培训机构

一万年没写DP了

这么简单的DP我居然没写出来

F - Erase Subarrays (atcoder.jp)

题意：

 思路：

原本的思路是这样的：

看到3000的数据范围就是n^2的DP了

看到删子串，那么留下来的就是子序列，要使得剩下来的子序列的和为x，那么就按这个子序列来DP

设dp[i][j]为前i个数，以ai为结尾的子序列，和为j的最少段数

然后转移就是枚举ai前面那个元素的位置，然后这是n^3的，所以也要用pre[i][j]数组记录前i个和为j的dp[i][j]

这样是错的，因为我不会转移QwQ

事实上，我们直接按题意状态设计就行

设dp[i][j]为前i个数，保留的和为j的最少操作次数

然后按照是否保留ai分类讨论

如果保留，就由dp[i-1][j-a[i]]转移过来

如果删掉，就去枚举删除的最后一段的长度

然后用pre[i][j]维护前i个数，保留的和为j的最小dp[i][j]

具体看代码：

#include <bits/stdc++.h>//#define int long longusing namespace std;const int mxn=3e3+10;int N,M;
int a[mxn],dp[mxn][mxn];//前i个数，保留和为j的最少操作次数 
int pre[mxn][mxn];signed main(){cin>>N>>M;for(int i=1;i<=N;i++) cin>>a[i];memset(dp,0x3f,sizeof(dp));memset(pre,0x3f,sizeof(pre));dp[0][0]=0;pre[0][0]=0;for(int i=1;i<=N;i++){for(int j=0;j<=M;j++){if(j>=a[i]) dp[i][j]=min(dp[i][j],dp[i-1][j-a[i]]);dp[i][j]=min(dp[i][j],pre[i-1][j]+1);pre[i][j]=min(pre[i-1][j],dp[i][j]);}}for(int i=1;i<=M;i++){if(dp[N][i]==0x3f3f3f3f) cout<<-1<<'\n';else cout<<dp[N][i]<<'\n';}
}