用代码块功能插入代码，请勿粘贴截图
这提是2018年noip提高组初赛题的最后一个填空题。程序的下半段采用动态规划，f记录状态，有几个问题不明白：
1.怎么理解状态转移方程f[j]= min(f[j]+b[i],j>=a[i]? f[j-a[i]]:Inf)中的f[j-a[i]]的含义，为何不是f[j-a[i]]+a[i]
2.有介绍说，这里的f[j]，其实是f[i-1][j]的简化，那么当i=0时，f[i-1][j]该如何解释？
完整的代码如下
#include
using namespace std;
const int Inf = 1000;
const int threshold = 410;
const int maxn = 8;
int n=8;
int a[maxn]={30,60,30,40,50,60,70,60};//450*0.95=427.5
int b[maxn]={30,60,60,60,70,80,90,70};
bool put_a[maxn];
int total_a, total_b;
double ans;
double f[threshold];//这个是重点:f[i]表示从当前前缀状态下，买总价格为i的物品，所需要去b商场的最小花费
double min(double x,double y){return x>y?y:x;}
int main(){//16行
int i;
// scanf("%d", &n);
// total_a = total_b = 0; //18行
for (i = 0; i < n; ++i) {
// scanf("%d%d", a + i, b + i);
if (a[i] <= b[i]) total_a += a[i]; //选价格小的，不考虑优惠
else total_b += b[i];
}
ans = total_a + total_b; //不考虑优惠,直接计算总价
total_a = total_b = 0;
for (i = 0; i < n; ++i){
if (a[i] * 0.95 <= b[i]){//买a
put_a[i] = true;
total_a += a[i];
}else{ //买b
put_a[i] = false;
total_b += b[i];
}
}
if (total_a >= threshold){//35行 a商品打折后> threshold,结束
printf("%.2f", total_a * 0.95 + total_b);
return 0;
}
f[0] = 0; //total_a < threshold
for (i = 1; i < threshold; ++i)
f[i] = Inf;
int total_b_prefix = 0;
for (i = 0; i < n; ++i)
if (!put_a[i]) { //如果是b买的，就考虑背包转移
total_b_prefix += b[i]; //当前去b买的物品，所花费的总代价
for (int j = threshold-1; j >= 0; --j) {
if (total_a+j+a[i]>=threshold && f[j]!= Inf)//如果可以转移
ans=min(ans,(total_a+j+a[i])*0.95+f[j]+total_b-total_b_prefix);
//当前去a商场的总花费加上背包体积以及当前物品，乘以折扣，在加上去b商场购买的总价值，是否小于ans
f[j]= min(f[j]+b[i],j>=a[i]? f[j-a[i]]:Inf);//背包转移
//考虑当前的j大小的背包是加上b[i]更优,还是直接靠f[j-a[i]]转移更优（就是考虑当前的背包是加上代价还是状态转移）
}
}
printf("%f", ans);
return 0;
}
