【分段DP】ABC275 F

叁歲伎倆 2024-03-22 09:11 48阅读 0赞

**一万年没写DP了**

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

[F - Erase Subarrays (atcoder.jp)][F - Erase Subarrays _atcoder.jp]

题意：

![cc962cc4c295425e9230ab09b1dd27c1.png][]

思路：

原本的思路是这样的：

看到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 long
    
    using 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';
    	}
    }

[F - Erase Subarrays _atcoder.jp]: https://atcoder.jp/contests/abc275/tasks/abc275_f
[cc962cc4c295425e9230ab09b1dd27c1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/5365f216919e491c85bfcf0bdc70ecce.png