Educational Codeforces Round 170 (Rated for Div. 2) D 题解

to sum of:前三题都是究极水题，补补D题吧，dp太钛肽弱了..

Problem - D - Codeforces--Attribute Checks

思路:首先得坚定地确定m^2,然后剩下的复杂度思考怎么优化..

key:每一个0只考虑影响到下一个0之间的数字!!
定义dp[i][j]为,在有i个能力点时.点了j个智力,那么点了i-j个力量.
在每一个0到下一个0之间的数字,可以用桶+差分来维护,这样可以o(1)查询在j智力情况下可以增加多少答案

看起来是n的循环里面嵌套了m的循环，但是m不是每次都执行的，只会执行m次，并且最坏的一次是m^2的。所以复杂度是加起来的，不是乘起来的，一下不留意可能算错时间复杂度..

int n,m;
int arr[2000006];
int bucket1[5005];  //用差分来优化o(1),区间修改的操作,如果用树状数组的话就是o(logn)的
int bucket2[5005];  key:每次只考虑两个0之间的检查!!这样不会算重算漏!!
int dp[5005][5005];  //定义dp[i][j]为,在有i个能力点时.点了j个智力,那么点了i-j个力量.
...坚定地确定m^2,然后剩下的复杂度思考怎么优化..
key:每一个0只考虑影响到下一个0之间的数字!!
可以优化成滚动数组,懒得搞了.
void solve(){       //D  o(m^2+n) or o(m^2logn+n)cin>>n>>m;for(int i=1;i<=n;i++) cin>>arr[i];int cntp=0,ans=0;int bk1=0,bk2=0;for(int i=1;i<=n+1;i++){  //到n+1是要处理最近一个0.即在末尾添加一个虚0.if(arr[i]==0){ //只会执行m次if(cntp==0){ cntp++; continue; }  //否则cntp-1会越界!!for(int j=1;j<=cntp;j++) bucket1[j]+=bucket1[j-1],bucket2[j]+=bucket2[j-1];for(int j=0;j<=cntp;j++){  //o(m^2)bk1=bucket1[j],bucket1[j]=0;  //两个0之间,bk2=bucket2[cntp-j],bucket2[cntp-j]=0;dp[cntp][j]=dp[cntp-1][max(0ll,j-1)]+bk1+bk2;  //本次点智力if(j<=cntp-1) dp[cntp][j]=max(dp[cntp][j],dp[cntp-1][j]+bk1+bk2); //本次点力量}cntp++;}if(arr[i]>0&&arr[i]<=cntp) bucket1[arr[i]]++;if(arr[i]<0&&-arr[i]<=cntp) bucket2[-arr[i]]++;}for(int j=0;j<=cntp-1;j++) ans=max(ans,dp[cntp-1][j]); //最后一个0是虚的.cout<<ans;
}