第三届河南省程序设计大赛 ——F BUYING FEED （动态规划）

太过爱你忘了你带给我的痛 2022-02-13 04:59 210阅读 0赞

## 题目描述: ##

Farmer **John** needs to travel to town to pick up K (1 <= K <= 100)pounds of feed. Driving D miles with K pounds of feed in his truck costs **D\*K**cents.

The county feed lot has N (1 <= N<= 100) stores (conveniently numbered 1..N) that sell feed. Each store is located on a segment of the X axis whose length is E (1 <= E <= 350). Store i is at location X\_i (0 < X\_i < E) on the number line and can sell **John** as much as F\_i (1 <= F\_i <= 100) pounds of feed at a cost of C\_i (1 <= C\_i <= 1,000,000) cents per pound.  
Amazingly, a given point on the X axis might have more than one store.

Farmer **John**  starts at location 0 on this number line and can drive only in the positive direction, ultimately arriving at location E, with at least **K** pounds of feed. He can stop at any of the feed stores along the way and buy any amount of feed up to the the store's limit. What is the minimum amount Farmer **John** has to pay to buy and transport the K pounds of feed? Farmer **John**  
knows there is a solution. Consider a sample where Farmer **John** needs two pounds of feed from three stores (locations: 1, 3, and 4) on a number line whose range is 0..5:  
0 1 2 3 4 5  
\---------------------------------  
1 1 1 Available pounds of feed  
1 2 2 Cents per pound

It is best for **John** to buy one pound of feed from both the second and third stores. He must pay two cents to buy each pound of feed for a total cost of 4. When **John** travels from 3 to 4 he is moving 1 unit of length and he has 1 pound of feed so he must pay1\*1 = 1 cents.

When **John** travels from 4 to 5 heis moving one unit and he has 2 pounds of feed so he must pay 1\*2 = 2 cents. The total cost is 4+1+2 = 7 cents.

## 输入描述: ##

<span style="color:#000000"> The first line of input contains a number c giving the number of cases that follow
    There are multi test cases ending with EOF.
    Each case starts with a line containing  three space-separated integers: K, E, and N
    Then N lines follow  :every line contains three space-separated integers:  Xi   Fi   Ci
    </span>

## 输出描述: ##

<span style="color:#000000">For each case,Output A single integer that is the minimum cost for FJ to buy and  transport the feed</span>

## 样例输入: ##

复制

1
    2 5 3                 
    3 1 2
    4 1 2
    1 1 1

## 样例输出: ##

### 第一种做法： ###

### 三层for循环的动态规划 ###

### 第二种做法： ###

### 一层for循环，将单价加上路程创造新的单价（代码在最后） ###

这是一个典型的动态规划，使用book数组记录最小费用，book\[i\]\[j\]的值代表其司机开过第i个商店后，车上货物为j时的最小费用

需要注意的是，在判断更新处理book\[i\]\[j\]时，若j>Fi，则第三层循环应从j-Fi开始

ac代码：

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<set>
    #include<map>
    #include<queue>
    #define INF 99999999
    using namespace std;
    struct store{         //设置结构体
    	int x,f,c,h;      //其中h代表到达此商店后，最多能有多少商品
    };
    bool cmp(struct store s1,struct store s2){  //设置排序规则
    	return s1.x<s2.x;
    }
    int main()
    {
    	int C,k,e,n;
    	while(scanf("%d",&C)!=EOF){
    		while(C--){
    			cin>>k>>e>>n;
    			struct store st[n+2];
    			int book[n+2][k+1];
    			fill(book[0],book[0]+(n+2)*(k+1),INF);  //将book数组初始化为INF
    			for(int i=0;i<n;i++){
    				scanf("%d%d%d",&st[i].x,&st[i].f,&st[i].c); 
    			}
    			st[n].x=e;
    			st[n].f=0;
    			st[n].c=INF;  //将终点模拟成一个不可购买商品的商店
    			sort(st,st+n+1,cmp);  //需要将商品按照到终点的距离排序，这关系到司机到达的顺序
    			for(int i=0;i<=st[1].f;i++){ //先将到达第一个商店后可能发生的情况填入
    				book[0][i]=i*st[0].c;
    			}      
    			st[0].h=st[0].f;   //将经过第一个商店之后的商品数量上限更新
    			for(int i=1;i<=n;i++){
    				st[i].h=st[i-1].h+st[i].f;  //将经过第i个商店之后的商品数量上限更新
    				for(int j=0;j<=k&&j<=st[i].h;j++){ //到达第i个商店时，车上可能有0——h个商品，但最多不超过k
    					if(j<=st[i].f){   //这个判断很重要，是区分此时在商店i能不能全部购买j件商品
    					    for(int k1=0;k1<=st[i-1].h&&k1<=j;k1++){
    						    if(book[i][j]>book[i-1][k1]+(j-k1)*st[i].c+k1*(st[i].x-st[i-1].x)){
    						    	book[i][j]=book[i-1][k1]+(j-k1)*st[i].c+k1*(st[i].x-st[i-1].x);
    						    }
    					    }
    					}else{
    						for(int k1=j-st[i].f;k1<=st[i-1].h&&k1<=j;k1++){
    						    if(book[i][j]>book[i-1][k1]+(j-k1)*st[i].c+k1*(st[i].x-st[i-1].x)){
    						    	book[i][j]=book[i-1][k1]+(j-k1)*st[i].c+k1*(st[i].x-st[i-1].x);
    						    }
    					    }
    						
    					}
    				}
    			}
    			cout<<book[n][k]<<endl;
    		}
    	}
    	return 0; 
    }

第二种做法：

由于无论在哪买商品都得运送到终点，索性就将单价加上运输费用作为新单价，并按照新单价从小到大排序，排序完成后先从新单价最少的商店购买，若在此商店买不够k，则取下一家买，直至买够k

ac代码：

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    using namespace std;
    struct store{
    	int x,f,c;
    };
    bool cmp(struct store s1,struct store s2){
    	return s1.c<s2.c;
    }
    int main()
    {
    	int C,k,e,n;
    	while(scanf("%d",&C)!=EOF){
    		while(C--){
    			cin>>k>>e>>n;
    			struct store st[n+2];
    			for(int i=0;i<n;i++){
    				scanf("%d%d%d",&st[i].x,&st[i].f,&st[i].c);
    				st[i].c+=e-st[i].x;  //因为无论在哪个商店买东西都需要运送到终点，索性将单价加上路程费用创造新的单价， 
    			}
    			sort(st,st+n,cmp);  //将商店按照新单价 从小到排序 
    			int sum1=0;
    			for(int i=0;i<n;i++){  //从新单价最小的买起，直至满足k 
    				if(k>st[i].f){     //若k大于当前商店最大销售量，则直接买完 
    					sum1+=st[i].f*st[i].c;    
    					k-=st[i].f;
    				}else{             //能在此商店达到购买量k，则买到k，退出循环 
    					sum1+=k*st[i].c;
    					break; 
    				} 
    			}
    			cout<<sum1<<endl;
    		}
    	}
    	return 0; 
    }