求助
  • 板块学术版
  • 楼主lc_lca
  • 当前回复7
  • 已保存回复7
  • 发布时间2020/5/5 21:02
  • 上次更新2023/11/7 03:04:26
查看原帖
求助
120340
lc_lca楼主2020/5/5 21:02

各位大佬,我这份代码为什么运行不了,谢谢!

#include<iostream>
#include<deque>
#define int long long
using namespace std;
const int maxn=5510;
int n,w,s;
int a[maxn];
int dp[maxn][maxn];
deque< pair<int,int> >q;
signed main()
{
    cin>>n>>w>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    dp[1][1]=a[1];
    for(int i=2;i<=n;i++)
    {
        //j=1 k=1~s
        while(!q.empty()) q.pop_back();
        //pair<int,int> first:id second:value
        for(int k=1;k<=s;k++)
        {
            dp[i][1]=max(dp[i][1],dp[i-1][k]+a[i]);
            int val=dp[i-1][k];
            while(q.back().second<val && !q.empty()) q.pop_back();
            q.push_back(make_pair(k,val));
        }
        //j k=(j-1)~(j+s-1)
        for(int j=2;j<=w;j++)
        {
            while(q.front().first<j-1 && !q.empty()) q.pop_front();
            int now=q.front().second;
            dp[i][j]=now+a[i]*j;
            if(j+s-1>w) continue;
            int k=j+s-1;
            int val=dp[i-1][k];
            while(q.back().second<val && !q.empty()) q.pop_back();
            q.push_back(make_pair(k,val));
        }
    }
    int ans=-1;
    for(int i=1;i<=w;i++)
    {
        ans=max(ans,dp[n][i]);
    }
    cout<<ans<<endl;
    return 0;
}

2020/5/5 21:02
加载中...