- 【调试程序】转移的时候要用原始值转移,复制一份数组或者从大到小枚举
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int r[2000005];
int s[2000005];
int d[5005],f[5005],g[5005];
int main()
{ios::sync_with_stdio(false);cin.tie(0);int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>r[i];s[i]=s[i-1]+(r[i]==0);}for(int i=1;i<=n;i++){if(r[i]==0){int cur=0;for(int j=0;j<s[i];j++){cur=cur+d[j];f[j]=f[j]+cur;d[j]=0;}memcpy(g,f,sizeof(f));for(int j=1;j<=s[i];j++){f[j]=max(g[j],g[j-1]);}}else{if(r[i]>0){if(r[i]<=s[i]){d[r[i]]++;}}else{if(s[i]+r[i]>=0){d[0]++;d[s[i]+r[i]+1]--;}}}}int cur=0;for(int j=0;j<=m;j++){cur=cur+d[j];f[j]=f[j]+cur;d[j]=0;}int ans=0;for(int i=0;i<=m;i++){ans=max(ans,f[i]);}cout<<ans<<endl;return 0;
}