Java 解法, 执行用时: 394ms, 内存消耗: 35944K, 提交时间: 2022-08-16 10:34:42

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int T=sc.nextInt();
        int MaxP=sc.nextInt();
        int W=sc.nextInt();
        int dp[][]=new int[2005][2005];
        int q[]=new int[2005];
        for (int i=0;i<=2000;i++)
        {
            for (int j=0;j<=2000;j++)
            {
                dp[i][j]=Integer.MIN_VALUE;
            }
        }
        for (int i=1;i<=T;i++)
        {
            int AP=sc.nextInt();
            int BP=sc.nextInt();
            int AS=sc.nextInt();
            int BS=sc.nextInt();
            for(int j=0;j<=AS;++j)   dp[i][j]=-j*AP;
            for(int j=0;j<=MaxP;++j) dp[i][j]=Math.max(dp[i][j],dp[i-1][j]);
            if (i<=W)continue;
            int l=1,r=0;
            for(int j=0;j<=MaxP;++j)
            {
                while(l<=r && q[l]<j-AS)  ++l;
                while(l<=r && dp[i-W-1][q[r]]+q[r]*AP<=dp[i-W-1][j]+j*AP) --r;
                q[++r]=j;
                dp[i][j]=Math.max(dp[i][j],dp[i-W-1][q[l]]+q[l]*AP-j*AP);
            }
            l=1;r=0;
            for(int j=MaxP;j>=0;--j)
            {
                while(l<=r && q[l]>j+BS)  ++l;
                while(l<=r && dp[i-W-1][q[r]]+q[r]*BP<=dp[i-W-1][j]+j*BP) --r;
                q[++r]=j;
                dp[i][j]=Math.max(dp[i][j],dp[i-W-1][q[l]]+q[l]*BP-j*BP);
            }
        }
        System.out.println(dp[T][0]);
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 41ms, 内存消耗: 16144K, 提交时间: 2020-08-23 11:35:31

#include<bits/stdc++.h>
#define Fox ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define turn_on_clock clock_t start,end;start=clock();
#define turn_off_clock end=clock();printf("\nTime eclipse:%.5lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
using namespace std;
const int N=1e4+10;
const int INF=0x3f3f3f3f;
int n,m,w,ap,bp,as,bs;
int dp[2005][2005],q[2005];
int main(){
	Fox;
	cin>>n>>m>>w;
	memset(dp,-INF,sizeof(dp));
	dp[0][0]=0;
	for(int i=1;i<=n;i++){
		cin>>ap>>bp>>as>>bs;
		for(int j=0;j<=m;j++)dp[i][j]=max(dp[i-1][j],dp[i][j]);
		int from=max(0,i-w-1);
		int l=1,r=0;
		for(int j=0;j<=m;j++){
			while(l<=r && q[l]<j-as)l++;
			while(l<=r && dp[from][q[r]]+q[r]*ap<dp[from][j]+j*ap)r--;
			q[++r]=j;
			dp[i][j]=max(dp[i][j],dp[from][q[l]]-(j-q[l])*ap);
		}
		l=1,r=0;
		for(int j=m;j>=0;j--){
			while(l<=r && q[l]>j+bs)l++;
			while(l<=r && dp[from][q[r]]+q[r]*bp<dp[from][j]+j*bp)r--;
			q[++r]=j;
			dp[i][j]=max(dp[i][j],dp[from][q[l]]-(j-q[l])*bp);
		}
	}
	cout<<dp[n][0];
	return 0;
}