单调队列优化 dp,WA on test #8 求调
查看原帖
单调队列优化 dp,WA on test #8 求调
400783
Nephren_Sakura楼主2022/7/26 14:34

rt

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int n=read(),m=read(),s=read(),a[1000005],dp[5005][5005];
signed main(){
    if(n/m>s){
        cout<<-1;
        return 0;
    }
    memset(dp,0xcf,sizeof(dp));
    int maxi=-1e18;
    for(int i=1; i<=n; i++)
        a[i]=read();//dp[0][i]=dp[i][0]=0;
    dp[0][0]=0;
    for(int i=1; i<=s; i++){
		deque<int> dq; 
    	for(int j=1; j<=n; j++){
        	while(dq.empty()==false&&dq.front()<j-m)
        		dq.pop_front();
        	while(dq.empty()==false&&dp[i-1][j-1]>=dp[i-1][dq.back()])
        		dq.pop_back();
        	dq.push_back(j-1);
        	dp[i][j]=dp[i-1][dq.front()]+a[j];
//            for(int k=1; k<=min(i,m); k++)
//                dp[i][j]=max(dp[i-k][j-1],dp[i][j]);
        }
    }
    int sum=-1e18;
    for(int i=n-m+1; i<=n; i++)
        sum=max(sum,dp[s][i]);
    cout<<sum;
    return 0;
}
2022/7/26 14:34
加载中...