Codeforces 1400 E. Clear the Multiset —— 暴力一眼DP

This way

题意:

给你长度为n的数组,你每次有两种操作:
l r 选择一个区间,将这个区间的每个位置的值-1
i x 选择一个点i,将这个点的值-x
问你要将这个数组清零最少要几次操作

题解:

数据范围5000,暗示的很明显了。首先考虑二维DP
dp[i][j]表示到了第i个位置,1操作的高度为j的时候的答案最小值(注意是高度而不是次数,因为中间可能有阻断的位置)
那么有三种转移的情况:dp[i-1][k(k<j)],dp[i-1][j],dp[i-1][k(k>j)]
但是每次暴力的转移复杂度是

O(n3)O(n^3)

O(n3),所以需要考虑优化
对于第一种情况,我们需要知到从哪里转移过来,因为我们要加上高度差值,如果去找的话,每次是

O(n)O(n)

O(n),但是我们从小往大做,每次实时地记录答案+差值的话,就可以

O(1)O(1)

O(1)转移,mi_pre就是干这个的。
第二种情况直接转移
第三种情况我们要注意,只有当a[i]<=n&&a[i-1]>=a[i]的时候才会有效,因为这样的话,就可能可以少掉一次2操作
需要从大到小做一遍,因为如果你从小到大做的话,然后从前面最大的后缀转移过来的话,你不知道那个位置是否比a[i]大。

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5,inf=1e8;
int dp[N][N],a[N],mi_suf[N];
int main()
{
int n;
scanf("%d",&n);
dp[0][0]=0;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
dp[i][j]=inf;
dp[0][0]=0;
mi_suf[n+1]=inf;
for(int i=n;~i;i--)
mi_suf[i]=min(mi_suf[i+1],dp[0][i]);
for(int i=1;i<=n;i++){
int mi_pre=dp[i-1][0];
for(int j=0;j<=min(n,a[i]);j++){
mi_pre++;
dp[i][j]=mi_pre+(j!=a[i]);
dp[i][j]=min(dp[i][j],dp[i-1][j]+(j!=a[i]));
mi_pre=min(mi_pre,dp[i-1][j]);
}
if(a[i]<=n&&a[i-1]>=a[i]){
mi_pre=mi_suf[a[i]];
for(int j=a[i];~j;j--){
dp[i][j]=min(dp[i][j],mi_pre);
if(mi_pre>dp[i-1][j])
mi_pre=dp[i-1][j]+1;
}
}
mi_suf[n+1]=inf;
for(int j=n;~j;j--)
mi_suf[j]=min(mi_suf[j+1],dp[i][j]);
}
int ans=inf;
for(int i=0;i<=n;i++)ans=min(ans,dp[n][i]);
printf("%d\n",ans);
return 0;
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

Codeforces 1400 E. Clear the Multiset —— 暴力一眼DP

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » Codeforces 1400 E. Clear the Multiset —— 暴力一眼DP
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏