那个网站可以做微课,地方网站程序,做签证宾馆订单用啥网站,个人做网站如何赚钱to sum of:前三题都是究极水题#xff0c;补补D题吧#xff0c;dp太钛肽弱了..
Problem - D - Codeforces--Attribute Checks
思路:首先得坚定地确定m^2,然后剩下的复杂度思考怎么优化..
key:每一个0只考虑影响到下一个0之间的数字!!
定义dp[i][j]为,在有i个能力点时.点了…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^2n) or o(m^2lognn)cinnm;for(int i1;in;i) cinarr[i];int cntp0,ans0;int bk10,bk20;for(int i1;in1;i){ //到n1是要处理最近一个0.即在末尾添加一个虚0.if(arr[i]0){ //只会执行m次if(cntp0){ cntp; continue; } //否则cntp-1会越界!!for(int j1;jcntp;j) bucket1[j]bucket1[j-1],bucket2[j]bucket2[j-1];for(int j0;jcntp;j){ //o(m^2)bk1bucket1[j],bucket1[j]0; //两个0之间,bk2bucket2[cntp-j],bucket2[cntp-j]0;dp[cntp][j]dp[cntp-1][max(0ll,j-1)]bk1bk2; //本次点智力if(jcntp-1) dp[cntp][j]max(dp[cntp][j],dp[cntp-1][j]bk1bk2); //本次点力量}cntp;}if(arr[i]0arr[i]cntp) bucket1[arr[i]];if(arr[i]0-arr[i]cntp) bucket2[-arr[i]];}for(int j0;jcntp-1;j) ansmax(ans,dp[cntp-1][j]); //最后一个0是虚的.coutans;
}
