3 solutions

  • 4
    @ 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≤106

    这种情况下，我们必须将查询的时间复杂度降为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最大为5002

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

    6.25*1010!!!!!

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

    怎么降呢？

    这时我们发现：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;
}

    比老师的方法简单

    • 1
      @ 2025-10-11 22:51:43

      说实话,现有题解的代码都太长了。。。

      我们设dpi,jdp_{i,j}为在花费不超过i元买了新鲜度至少为j的花时的最大美丽度：

      容易推出状态转移方程：

      $dp_{i,j}=max(dp_{i,j},dp_{i-co[k],j-max(0,j-fr[k])}+be[k])$

      其中k是现在遍历到了第k朵花(1≤k≤n1 \leq k \leq n)

      那就有人要问了:主播主播，为什么方程里的新鲜度部分是max(0,j−fr[k])max(0,j-fr[k])啊？

      很好理解,想一下我买完这朵花之后新鲜度的要求直接降到了负数,那实际上就是已经完全满足了对新鲜度的要求,和新鲜度要求为0时没有任何区别,故算到一起(其实就是离散化)

      代码部分,直接代入数据最大值做预处理,O(1)O(1)查询即可

      参考代码:

      #include<iostream>
#include<cstring>
using namespace std;
int n,q,co[505],be[505],fr[505],dp[505][505];
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>co[i]>>fr[i]>>be[i];
    memset(dp,-0x3f,sizeof(dp));
    for(int i=0;i<=500;i++) dp[i][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=500;j>=co[i];j--){
            for(int k=500;k>=0;k--){
                dp[j][k]=max(dp[j][k],dp[j-co[i]][max(0,k-fr[i])]+be[i]);
            }
        }
    }
    while(q--){
        int c,f;
        cin>>c>>f;
        cout<<max(0,dp[c][f])<<endl;
    }
    return 0;
}

      代码精简这一块

      • 0
        @ 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;
}
        • @ 2025-6-3 15:16:51

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

      • 1

      小挖的买花

      Information

      ID
      8018
      Time
      1000ms
      Memory
      512MiB
      Difficulty
      4
      Tags
      # Submissions
      102
      Accepted
      4
      Uploaded By
      1. About
      2. Contact Us
      3. Privacy
      4. Terms of Service
      5. Copyright Complaint
      6. Language
      7. Legacy mode
      8. Theme
      2. 粤ICP备2022044963号-1
      3. Worker 0, 25ms
      4. Powered by Hydro v4.13.3 Community