题意 : 有体积分别为x和y的物品以及n个空的箱子，第i个箱子有着bi的容量，先试图用这些箱子装物品，使装的物品总体积不小于r，同时对于每个箱子装完物品后的剩余容量Ci，希望求出箱子装完至少r体积物品后，所有箱子剩余体积Ci的平方和，可以取到的最大值是多少？如果用所给的箱子不能装下r体积的物品，则直接输出-1。
解题思路: 因为只有x和y这两种体积的物体，同时每个箱子的容量都已知，数据范围也较小(都是不超过100)，所以可以很方便的求出每个箱子能够容纳多少体积的物体，为了保证最终所求值较小，我们要使得所有箱子存放的物品容量在满足r的情况下尽可能小，因此当前箱子具体装多少对于后面箱子的存放存在干扰，采用动态规划(dp)的方式来解决最合适不过，我们设 dp[i][j] 代表第i个箱子存放j容量大小的物品需要多少个x y物品(其实就是判断这个箱子能否容纳这个体积的物品)， 再用 dpp[i][j]表示前i个箱子被用于存放物品后，当前已存入j体积物品时的剩余体积平方和，那么自然dpp[i][0]的初始值就是所有物品容量的平方和，之后分别用num ， j ，i顺序遍历r n 和 bi，确定在当前存放容量为num时，第j个箱子存放了体积和为i的物品后，此刻剩余容量和的最大值，关于递推式，我们容易判断当一个箱子容量为7时，还未放入任何物品的它将为答案贡献7*7的数值，而在它被放入2体积物品后，贡献值变成5*5，相较之前减少了(7*7) - (5*5) = 24 ,因此我们分析后的递推式将是dpp[j][num + i] = max(dpp[j][num+i] , dpp[j - 1][num] - (b[j]*b[j] - ( (b[j] - i)*(b[j] - i) ) ) ) ，最终所求答案将是dpp[n][r]，此外要判断这个值是否为负数，若是，说明我们达不到存放r体积物品的条件，直接输出“-1”即可，否则则直接输出该值即可。
AC代码
#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;
}