文章

4

粉丝

495

获赞

2

访问

31.0k

头像
最大报销额 - 普通解法
P1327 浙江大学机试题
发布于2021年3月5日 12:01
阅读数 8.1k

#include<bits/stdc++.h>
using namespace std;

int w;
char c;
float cost;     //记录价格
char type;      //记录类型

float dp[1005]; //动态规划数组

int main(){
	float q;
	int n;
	while(cin>>q>>n){
		if(n == 0) break;
		float a[n+1];     //数组存每个发票的总价格
		
		for(int i = 0;i<n;i++){
			cin>>w;
			
			float sum = 0;
			
			for(int j = 0;j<w;j++){
				
				cin>>type>>c>>cost;
				
			
				if(type == 'A' || type == 'B' || type == 'C'){
					if(cost>600) { //不是报销范围,报销价格置于0
						sum = 0;
						continue;
					}
					else sum += cost;
				}
				else{   //不是报销类型,报销价格置于0

					sum = 0;
					continue;
				}
			}
			
			if(sum<=1000) { //价格1000以内,放入数组
				a[i+1] = sum;
			}
		}//for


        //以下为动态规划找出最大报销值,类似于背包
		
		dp[1] = a[1];	
	
		for (int i = 2; i <= n; ++i){
			if(dp[i-1] + a[i] <= q)
				dp[i] = dp[i-1] + a[i];
			else 
				dp[i] = max(dp[i-1], dp[i-1] - a[i-1] + a[i]);
			
		}
		
...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发