文章
4
粉丝
495
获赞
2
访问
31.0k
#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]);
}
...
登录后发布评论
暂无评论,来抢沙发