2023CCPC华为云挑战赛 C-装箱问题

 #include<bits/stdc++.h>
#define int long long
using namespace std;
#pragma GCC optimize(3)
#pragma GCC optimize(2)
const int mod = 1e18;
const int inf = 1e10;
typedef long long ll;

int T , n , x , y , r , sum = 0;
int b[105];
int dpp[101][10001];
int dp[105][105];

signed main() {
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	//cout.tie(0);
	//cin >> T;
	scanf("%lld" , &T);
	while(T--) {
		scanf("%lld %lld %lld %lld" , &n , &x , &y , &r);
		sum = 0;
		for(int j = 1 ; j <= n ; j++){
			scanf("%lld" , &b[j]);
			sum += (b[j]*b[j]);//计算容量平方和
		}
		sort(b+1 , b+1+n);
		for(int j = 1 ; j <= 100 ; j++){
			dp[j][0] = 0;
			for(int i = 1 ; i <= 100 ; i++){
		    	dp[j][i] = mod;
		    }
		}
		for(int j = 1 ; j <= n ; j++){//计算每个箱子能够容纳多少体积的物品
			for(int i = 0 ; i <= b[j] ; i++){
				if(i + x <= b[j]){
				   dp[j][i + x] = min(dp[j][i + x] , dp[j][i] + 1);
				}
				if(i + y <= b[j]){
					dp[j][i + y] = min(dp[j][i + y] , dp[j][i] + 1);
				}
			}
		}
		for(int i = 0 ; i <= n ; i++){
			dpp[i][0] = sum;
			for(int j = 1 ; j <= r ; j++){
			  dpp[i][j] = -inf;//初始化，除了不存放外，其他情况都先定义为极小值。
		   }
		}
		for(int num = 0 ; num <= r ; num++){
		   for(int j = 1 ; j <= n ; j++){
		    	for(int i = 0 ; i <= b[j] ; i++){
				  if(dp[j][i] != mod){//保证这个物品可以存放i体积的物品
				  	if( num + i <= r ){//要注意加上这个存入量后是否超过r，超过r就直接对dpp[j][r]更新即可
				  		dpp[j][num + i] = max(dpp[j][num+i] ,  dpp[j - 1][num] - (b[j]*b[j] -  ( (b[j] - i)*(b[j] - i) )));
					}
					else{
						dpp[j][r] = max(dpp[j][r] ,  dpp[j - 1][num] - (b[j]*b[j] -  ( (b[j] - i)*(b[j] - i) )));
					}
				  }
				  else{
				  	continue;
				  }
			   }
	        } 
	    } 
		if(dpp[n][r] < 0){//判断能否满足题目要求，不能则输出-1
			cout<<"-1\n";
		}
		else{
			cout<<dpp[n][r]<<"\n";
		}
	}

	return 0;
}