第一题：（这题没写出来QAQ，我知道如何求x ^ ab的最大值，ab的值是多少）
给定一个数x，数据对 (a, b)使得a ^ b ^ x能达到最大，求使|a - b|最小的方案总数有多少。
x,a,b的范围都是0 - 2^31 次方
第二题：卖粽子（典型的背包问题）
小明要卖粽子，有m种粽子，n克面粉，多种馅料，求做出的粽子能够卖出价格最大是多少？
给定 a[] , b[], c[], d[]
其中a[i] 表示第 i 种粽子，现有馅料数目
b[i]表示第 i 种粽子，消耗多少馅料
c[i] 表示第 i 种粽子，消耗多少面粉
d[i] 表示第 i 种粽子，可以卖多少钱
ps：c[0] d[0] 表示不带陷的粽子要多少面粉，和值多少钱
有大佬看看我的代码吗？？？？只能通过10%，然后显示超时了，难道要用二进制优化或者单调队列优化吗？？？
import java.util.*;
public class Main {
//a馅料数目，b消耗馅料，c消耗面粉，d价格
public static int maxValue(int[] a, int[] b, int[] c, int[] d, int V) {
//bian li v
int[] f = new int[V + 1];
//bian li shu mu
for (int i = 0; i < a.length; i++) {
for (int j = V; j >= 0; j--) {
for (int k = 0; k * b[i] <= a[i] && k * c[i] <= j; k++) {
f[j] = Math.max(f[j - k * c[i]] + k * d[i], f[j]);
}
}
}
return f[V];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
int m = sc.nextInt();
//需要馅料
int[] a = new int[m + 1];
//消耗馅料
int[] b = new int[m + 1];
//面粉
int[] c = new int[m + 1];
//价格d
int[] d = new int[m + 1];
c[0] = sc.nextInt();
d[0] = sc.nextInt();
a[0] = 0;
b[0] = 0;
for (int i = 1; i <= m; i++) {
a[i] = sc.nextInt();
b[i] = sc.nextInt();
c[i] = sc.nextInt();
d[i] = sc.nextInt();
int res = maxValue(a, b, c, d, n);
System.out.println(res);
}
}
}
} 
全部评论
(11) 回帖