AcWing 734. 能量石
原题链接
困难
作者:
BBlone
,
2024-01-22 22:41:30
,
所有人可见
,
阅读 34
java 代码
import java.util.*;
public class Main{
//对于普通的背包问题
//我们从前i个物品选最终选取物品的先后顺序是无序的
//就是例如最后我选了编号为2 3 5的物品 最后最大价值 但是我不需要关心我选择他们的顺序 因为其先选后选并不会影响后面的价值
//所以我们可以按照题目默认的次序来进行选择
//但是这道题因为前面选择的物品会影响后面的价值所以我们要按一定顺序来选
//所以我们要枚举顺序来进行dp
//所以这道题是枚举顺序加dp求最大值
//我们最优解的顺序可以通过贪心来求 就是找规律 发现 按照此顺序进行dp会得到最优dp
// ##dp问题就是从所有方案组成的集合中选取最优解
// ##其实就是暴力搜索来组成所有方案
//这道题如果没有先能量减少的限制的话 就是时间在<=时间的情况下的价值最大的方案
//有了这一个约束 说明我们转化为以什么样的顺序吃能量石得到的能量最大或者吃哪些能量石最大
//我们以第一种思路来以什么样的顺序
//用贪心法 考虑最优解中任意相邻两个i i+1 吃的顺序的
//贪心应用就是最优子结构 就是每个子问题的最优解就是整体的
//我们发现如果先吃i必须保证SILI+1<Si+1l+转换一下变为si/li 小于后一个的
//为什么说任意相邻的符合这个顺序的整体就最优呢
//我们用反证法证明一下 如果最优解吃的顺序中前一个吃的要大于后一个我们交换一下位置那么总价值不就提升了吗
//贪心就是每次我们都吃价值最大的导致最后整体的价值最大
//贪心思维就是以局部最优来推导全局最优
//例如我们有10张纸币 我们取五次要求和最大
//那么我们每次都取最大就是五次和最大的
//要判断此问题是否符合贪心法就是局部最优——》全局最优我们可以用数学证明或者反证法
//例如这道题我么以什么样的顺序来吃能量石导致总能量最大
//我们吃的时候都选最大的
//但是我们选的最大后其他的能量会发生变化所以我们就有疑问是否符合贪心呢
//我们用反正法来证明一下
//我们每次选的相邻两个 第i个的能量为Ei+Ei+1-Si*li+1 第i+1 -Si+1-Si
//每次选最大也就是每个si*li+<static
//反证法整如果最大的能量方案中有一个的要大于它 那总体价值还有最大码
//反正法就和
// ##我们通过发现最优解中
//
static int N=10010;
static class Stone {
int s;
int e;
int l;
public Stone(int s,int e,int l){
this.s=s;
this.e=e;
this.l=l;
}
}
public static void main(String[] agrs){
Scanner in=new Scanner(System.in);
int T=in.nextInt();
//对每一个能量石按照si/li从小到达排序
//这里我们可以用结构体自动排序
for(int i=1;i<=T;i++){
int n=in.nextInt();
int m=0;
Stone[] st=new Stone[N];
int[] f=new int[N];
for(int j=1;j<=n;j++){
int s=in.nextInt();
int e=in.nextInt();
int l=in.nextInt();
m+=s;
st[j]=new Stone(s,e,l); //结构体排序就用内置的
}
Arrays.sort(st,1,n+1,(x,y)->x.s*y.l-x.l*y.s);
Arrays.fill(f,-12000000);
f[0]=0;
for(int k=1;k<=n;k++){
int s=st[k].s;
int e=st[k].e;
int l=st[k].l;
for(int j=m;j>=s;j--){
f[j]=Math.max(f[j],f[j-s]+e-(j-s)*l);
}
}
int res=0;
for(int w=0;w<=m;w++){
res=Math.max(res,f[w]);
}
System.out.println("Case #"+(i)+": "+res);
}
}
}
blablabla