C24chenzebang LV 3 @ 2025-6-3 19:41:22

#P8548. 小挖的买花

我像是小挖的nigger一样

题意

每次用有限的钱买花，要求花足够新鲜，在此条件下选最美的那组花。

思路

由于钱是有限的，花又要足够新鲜，所以可以当做二维费用做

钱的上限已给出，新鲜度的上限可以当所有花的新鲜度之和

所以

#include<bits/stdc++.h>
using namespace std;
int n,q,cost[510],fr[510],be[510],c,f,dp[510][250010],sum,maxbe;
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>cost[i]>>fr[i]>>be[i];
		sum+=fr[i];//计算新鲜度上限 
	}
	for(int i=1;i<=q;i++){
		maxbe=0;
		cin>>c>>f;
		for(int j=c;j>=0;j--){
			for(int k=sum;k>=0;k--){
				dp[j][k]=INT_MIN;//初始化dp数组 
			}
		}
		dp[0][0]=0;
		for(int j=1;j<=n;j++){
			for(int k=c;k>=cost[j];k--){
				for(int l=sum;l>=fr[j];l--){
					//遍历二维费用 
					if(dp[k-cost[j]][l-fr[j]]!=INT_MIN){
					    dp[k][l]=max(dp[k-cost[j]][l-fr[j]]+be[j],dp[k][l]);
					}
					if(f<=l){
						maxbe=max(maxbe,dp[k][l]);
					}
				}
			}
		}
		cout<<maxbe<<endl;
	}                             
	return 0;
}

但是40WA,其他全部TLE

注意到q的数据范围：1≤q≤10⁶

这种情况下，我们必须将查询的时间复杂度降为O(1)

所以要预处理dp和最大值数组

代码如下

#include<iostream>
#include<climits>
using namespace std;
int n,q,cost[510],fr[510],be[510],c,f,dp[510][21210],sum,maxbe[510][250010];
int main(){ 
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>cost[i]>>fr[i]>>be[i];
		sum+=fr[i];//计算新鲜度上限 
	}
	for(int j=505;j>=0;j--){
		for(int k=sum;k>=0;k--){
			dp[j][k]=INT_MIN;//初始化dp数组 
		}
	}
	dp[0][0]=0;
	//预处理dp数组 
    for(int j=1;j<=n;j++){
		for(int k=505;k>=cost[j];k--){
			for(int l=sum;l>=fr[j];l--){
				if(dp[k-cost[j]][l-fr[j]]!=INT_MIN){
					//遍历二维费用 
					dp[k][l]=max(dp[k-cost[j]][l-fr[j]]+be[j],dp[k][l]);
				}
			}
		}
	}
	//前缀和预处理最大值数组 
    for(int i=0;i<=505;i++){
        for(int j=0;j<=sum;j++){
        	if(i==0)maxbe[i][j]=dp[i][j];
            else maxbe[i][j]=max(dp[i][j],maxbe[i-1][j]);
        }
    }                                              
    for(int i=0;i<=505;i++){
        for(int j=sum-1;j>=0;j--){
            maxbe[i][j]=max(maxbe[i][j],maxbe[i][j+1]);
        }
    }
	for(int i=1;i<=q;i++){
		cin>>c>>f;
		if(f>sum)cout<<0<<endl;
		else cout<<max(maxbe[c][f],0)<<endl;
	}                             
	return 0;
}

但是80WA，还是有两个测试用例TLE

注意到3≤n≤500，0≤cost,fr,cj≤500

也就是说sum最大为500²

那么预处理时间复杂度......

6.25*10¹⁰!!!!!

所以还要降预处理时间复杂度

怎么降呢？

这时我们发现：0≤f≤500

在要求新鲜度小于等于500的情况下，500以上的新鲜度数组没有任何用处

所以我们可以在遍历每一朵花的时候，将上一朵花大于500的新鲜度存进500新鲜度的dp数组里

由于:0≤f≤500

所以我们可以将内层循环改为500+500=1000

代码如下:

#include<iostream>
#include<climits>
using namespace std;
int n,q,cost[510],fr[510],be[510],c,f,dp[510][1010],sum,maxbe[510][1010];//数组第二维大小改为1010
int main(){    
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>cost[i]>>fr[i]>>be[i];
		sum+=fr[i];//计算新鲜度最大值
	}
	for(int j=505;j>=0;j--){
		for(int k=1000;k>=0;k--){
			dp[j][k]=INT_MIN;//初始化dp数组
		}
	}
	dp[0][0]=0;
    for(int j=1;j<=n;j++){
		for(int k=505;k>=cost[j];k--){
			for(int l=1000;l>=fr[j];l--){
        //内层循环改为1000，正常二维费用
				if(dp[k-cost[j]][l-fr[j]]!=INT_MIN){
					dp[k][l]=max(dp[k-cost[j]][l-fr[j]]+be[j],dp[k][l]);
				}
			}
		}
		for(int k=505;k>=cost[j];k--){
			for(int l=1000;l>=500;l--){
				dp[k][500]=max(dp[k][500],dp[k][l]);//将大于500的新鲜度存进500里
			}
		}	
	}
  //前缀和预处理最大值数组(由于dp数组内层循环改为1000，所以可以在处理最大值时也将内层循环改为1000)
    for(int i=0;i<=505;i++){
        for(int j=0;j<=1000;j++){
        	if(i==0)maxbe[i][j]=dp[i][j];
            else maxbe[i][j]=max(dp[i][j],maxbe[i-1][j]);
        }
    }         
    for(int i=0;i<=505;i++){
        for(int j=999;j>=0;j--){
            maxbe[i][j]=max(maxbe[i][j],maxbe[i][j+1]);
        }
    }   
	for(int i=1;i<=q;i++){
		cin>>c>>f;
		if(f>sum)cout<<0<<endl;
		else cout<<max(maxbe[c][f],0)<<endl;
	}                             
	return 0;
}

比老师的方法简单

h_h LV 6 @ 2025-5-31 12:25:35

/*
input1
16 16
13 190 150519
487 278 963895
311 445 999567
277 277 656425
82 232 970123
351 64 393056
492 468 329210
370 123 446733
190 452 542659
86 226 511286
14 43 855461
98 283 14229
355 145 418112
341 478 179540
246 263 518758
280 468 664876
322 288
87 400
352 117
282 162
344 411
464 143
221 141
172 268
183 5
450 328
288 67
361 59
152 242
250 324
6 73
458 145

output1
2518762
0
2518762
2487389
2518762
3030048
2487389
1976103
2336870
3030048
2487389
2518762
1976103
2487389
0
3030048

input2
2 3
1 1 1
2 2 2
3 4
3 3 
3 2

output2
0
3
3 
*/
//典型的限制性二维费用01背包问题.对于限制最小值操作，空间消耗无法确定，如果直接开肯定 MLE
//将 ≥500 的新鲜度所带来的最优方案都存放到 501 的新鲜度中
//q≤1E6，我们要做到 O(1) 查询（易错点：这涉及区间查询，注意不是单点查询！！！），我们就要统计前缀最大值（当前花费c可以取更少c的最优值）和后缀最大值（当前新鲜度f可以取更高f的最优值）。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <climits>

//#define MAX_N 5
//#define MAX_COST 5
//#define MAX_FR 5
#define MAX_N 501
#define MAX_COST 501
#define MAX_FR 501
int cost[MAX_N], fr[MAX_N], be[MAX_N];
using namespace std;
int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; ++i)	scanf("%d %d %d", &cost[i], &fr[i], &be[i]);

    // Dynamic programming table: dp[c][f] = maximum beauty sum for cost c and freshness f
    int dp[MAX_COST][MAX_FR];
//    memset(dp, 0, sizeof(dp));//本题都是正数，比较方便，极小值ninf是0 
	for(int c = 0; c < MAX_COST; ++c){
		for(int f = 0; f < MAX_FR; ++f){
			dp[c][f]=INT_MIN; 
		}
	}
	dp[0][0]=0;

    for (int i = 1; i <= n; ++i) {
        int c = cost[i];
        int f = fr[i];
        int b = be[i];
		for(int j = MAX_COST - 1; j >= c; --j){
			for(int k = MAX_FR - 1; k >= MAX_FR - f - 1; --k){//限制性最小值阈值特殊处理：将>=500的都视为500处理,k取值范围为[MAX_FR - f - 1, MAX_FR - 1]时加上f必然>=MAX_FR - 1
				dp[j][MAX_FR - 1] = max(dp[j][MAX_FR - 1], dp[j-c][k] + b);
			}
			for(int k = MAX_FR - 2; k >= f; --k){//正常二维费用 
				dp[j][k] = max(dp[j][k], dp[j-c][k-f] + b);
			}
		}
    }
//	for(int c = 0; c < 5; ++c){
//		for(int f = 0; f < 5; ++f){
//			printf("%4d ", dp[c][f]);
//		}
//		printf("\n");
//	}

    // Precompute the maximum beauty for each cost and minimum freshness
    int max_beauty[MAX_COST][MAX_FR];
    memset(max_beauty, 0, sizeof(max_beauty));
	for(int c = 0; c < MAX_COST; ++c){
		max_beauty[c][MAX_FR - 1] = dp[c][MAX_FR - 1];
		for(int f = MAX_FR - 2; f >= 0; --f){
			max_beauty[c][f]=max(dp[c][f], max_beauty[c][f+1]);
		} 
	} 
	for(int f = MAX_FR - 1; f >= 0; --f) max_beauty[0][f]=max(max_beauty[0][f], 0);
	for(int c = 1; c < MAX_COST; ++c){
		for(int f = MAX_FR - 1; f >= 0; --f){
			max_beauty[c][f]=max(max_beauty[c][f], max_beauty[c-1][f]);
		} 
	} 
	while(q--){
		int C, F;
		scanf("%d %d", &C, &F);
		printf("%d\n", max_beauty[C][F]);
	}
    return 0;
}/*
input1
16 16
13 190 150519
487 278 963895
311 445 999567
277 277 656425
82 232 970123
351 64 393056
492 468 329210
370 123 446733
190 452 542659
86 226 511286
14 43 855461
98 283 14229
355 145 418112
341 478 179540
246 263 518758
280 468 664876
322 288
87 400
352 117
282 162
344 411
464 143
221 141
172 268
183 5
450 328
288 67
361 59
152 242
250 324
6 73
458 145

output1
2518762
0
2518762
2487389
2518762
3030048
2487389
1976103
2336870
3030048
2487389
2518762
1976103
2487389
0
3030048

input2
2 3
1 1 1
2 2 2
3 4
3 3 
3 2

output2
0
3
3 
*/
//典型的限制性二维费用01背包问题.对于限制最小值操作，空间消耗无法确定，如果直接开肯定 MLE
//将 ≥500 的新鲜度所带来的最优方案都存放到 501 的新鲜度中
//q≤1E6，我们要做到 O(1) 查询（易错点：这涉及区间查询，注意不是单点查询！！！），我们就要统计前缀最大值（当前花费c可以取更少c的最优值）和后缀最大值（当前新鲜度f可以取更高f的最优值）。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <climits>

//#define MAX_N 5
//#define MAX_COST 5
//#define MAX_FR 5
#define MAX_N 501
#define MAX_COST 501
#define MAX_FR 501
int cost[MAX_N], fr[MAX_N], be[MAX_N];
using namespace std;
int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; ++i)	scanf("%d %d %d", &cost[i], &fr[i], &be[i]);

    // Dynamic programming table: dp[c][f] = maximum beauty sum for cost c and freshness f
    int dp[MAX_COST][MAX_FR];
//    memset(dp, 0, sizeof(dp));//本题都是正数，比较方便，极小值ninf是0 
	for(int c = 0; c < MAX_COST; ++c){
		for(int f = 0; f < MAX_FR; ++f){
			dp[c][f]=INT_MIN; 
		}
	}
	dp[0][0]=0;

    for (int i = 1; i <= n; ++i) {
        int c = cost[i];
        int f = fr[i];
        int b = be[i];
		for(int j = MAX_COST - 1; j >= c; --j){
			for(int k = MAX_FR - 1; k >= MAX_FR - f - 1; --k){//限制性最小值阈值特殊处理：将>=500的都视为500处理,k取值范围为[MAX_FR - f - 1, MAX_FR - 1]时加上f必然>=MAX_FR - 1
				dp[j][MAX_FR - 1] = max(dp[j][MAX_FR - 1], dp[j-c][k] + b);
			}
			for(int k = MAX_FR - 2; k >= f; --k){//正常二维费用 
				dp[j][k] = max(dp[j][k], dp[j-c][k-f] + b);
			}
		}
    }
//	for(int c = 0; c < 5; ++c){
//		for(int f = 0; f < 5; ++f){
//			printf("%4d ", dp[c][f]);
//		}
//		printf("\n");
//	}

    // Precompute the maximum beauty for each cost and minimum freshness
    int max_beauty[MAX_COST][MAX_FR];
    memset(max_beauty, 0, sizeof(max_beauty));
	for(int c = 0; c < MAX_COST; ++c){
		max_beauty[c][MAX_FR - 1] = dp[c][MAX_FR - 1];
		for(int f = MAX_FR - 2; f >= 0; --f){
			max_beauty[c][f]=max(dp[c][f], max_beauty[c][f+1]);
		} 
	} 
	for(int f = MAX_FR - 1; f >= 0; --f) max_beauty[0][f]=max(max_beauty[0][f], 0);
	for(int c = 1; c < MAX_COST; ++c){
		for(int f = MAX_FR - 1; f >= 0; --f){
			max_beauty[c][f]=max(max_beauty[c][f], max_beauty[c-1][f]);
		} 
	} 
	while(q--){
		int C, F;
		scanf("%d %d", &C, &F);
		printf("%d\n", max_beauty[C][F]);
	}
    return 0;
}

h_h @ 2025-6-3 15:16:51

max_beauty直接复用dp就好，这里是为了强调预处理过程多开个数组

ID

8018

Time

1000ms

Memory

512MiB

Difficulty

Tags

# Submissions

101

Accepted

Uploaded By

Hydro

2 solutions

#P8548. 小挖的买花

我像是小挖的nigger一样

题意

每次用有限的钱买花，要求花足够新鲜，在此条件下选最美的那组花。

思路

由于钱是有限的，花又要足够新鲜，所以可以当做二维费用做

钱的上限已给出，新鲜度的上限可以当所有花的新鲜度之和

所以

但是40WA,其他全部TLE

注意到q的数据范围：1≤q≤10⁶

这种情况下，我们必须将查询的时间复杂度降为O(1)

所以要预处理dp和最大值数组

代码如下

但是80WA，还是有两个测试用例TLE

注意到3≤n≤500，0≤cost,fr,cj≤500

也就是说sum最大为500²

那么预处理时间复杂度......

6.25*10¹⁰!!!!!

所以还要降预处理时间复杂度

怎么降呢？

这时我们发现：0≤f≤500

在要求新鲜度小于等于500的情况下，500以上的新鲜度数组没有任何用处

所以我们可以在遍历每一朵花的时候，将上一朵花大于500的新鲜度存进500新鲜度的dp数组里

由于:0≤f≤500

所以我们可以将内层循环改为500+500=1000

代码如下:

比老师的方法简单

小挖的买花

Information

Status

Development

Support

2 solutions

#P8548. 小挖的买花

我像是小挖的nigger一样

题意

每次用有限的钱买花，要求花足够新鲜，在此条件下选最美的那组花。

思路

由于钱是有限的，花又要足够新鲜，所以可以当做二维费用做

钱的上限已给出，新鲜度的上限可以当所有花的新鲜度之和

所以

但是40WA,其他全部TLE

注意到q的数据范围：1≤q≤106

这种情况下，我们必须将查询的时间复杂度降为O(1)

所以要预处理dp和最大值数组

代码如下

但是80WA，还是有两个测试用例TLE

注意到3≤n≤500，0≤cost​,fr,cj≤500

也就是说sum最大为5002

那么预处理时间复杂度......

6.25*1010!!!!!

所以还要降预处理时间复杂度

怎么降呢？

这时我们发现：0≤f≤500

在要求新鲜度小于等于500的情况下，500以上的新鲜度数组没有任何用处

所以我们可以在遍历每一朵花的时候，将上一朵花大于500的新鲜度存进500新鲜度的dp数组里

由于:0≤f≤500

所以我们可以将内层循环改为500+500=1000

代码如下:

比老师的方法简单

小挖的买花

Information

Status

Development

Support

Don't have an account?

SIGN IN

注意到q的数据范围：1≤q≤10⁶

注意到3≤n≤500，0≤cost,fr,cj≤500

也就是说sum最大为500²

6.25*10¹⁰!!!!!