蓝桥杯Java ABC组 LG P1336 最佳课题选择
题目链接:
https://www.luogu.com.cn/problem/P1336
#背包问题
一道经典的泛化物品的背包问题
本题的泛化物品:每个课题是一个物品,对于每个课题物品,当体积为 x x x 时,价值为 A i × x B i A_i\times x^{B_i} Ai×xBi
而本题题意所求的就是:体积恰好为 n 的情况下,价值的最小值
注意“恰好”和“最小值”的限制
[!danger]
十年 OI 一场空,不开 __ __ 见祖宗
代码
import java.io.*;
import java.util.*;
import static java.lang.Math.*;
public class Main{
static int status;
static BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static PrintWriter cout = new PrintWriter(bw);
static StreamTokenizer st = new StreamTokenizer(buf);
public static int nextInt() throws IOException {
status = st.nextToken();
return (int) st.nval;
}
public static long nextLong() throws IOException {
status = st.nextToken();
return (long) st.nval;
}
public static String nextString() throws IOException {
status = st.nextToken();
return st.sval;
}
static final int INF = 0x3f3f3f3f, MOD = (int) 1e9 + 7;
static int n, m;
static int[] a,b;
static long[] f;
public static void main(String[] args) throws IOException {
n = nextInt();
m = nextInt();
a = new int[m+1];
b = new int[m+1];
f = new long[n+1];
Arrays.fill(f,Long.MAX_VALUE/2);
for(int i=1;i<=m;i++){
a[i] = nextInt();
b[i] = nextInt();
}
f[0]=0;
for(int i=1;i<=m;i++)
for(int j=n;j>=1;j--)
for(int k=1;k<=j;k++)
f[j]=min(f[j],f[j-k]+a[i]*(long)pow(k,b[i]));
cout.println(f[n]);
cout.flush();
}// End of main
}
原文地址:https://blog.csdn.net/qq_36992525/article/details/136933455
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!