A39797. 移动办公
填空题
困难
知识点
题目描述
移动办公
题目描述
假设你经营着一家公司，公司在北京和南京各有一个办公地点。公司只有你一个人，所以你只能每月选择在一个城市办公。在第i个月，如果你在北京办公，你能获得Pi的营业额，如果你在南京办公，你能获得Ni的营业额。但是，如果你某个月在一个城市办公，下个月在另一个城市办公，你需要支付M的交通费。那么，该怎样规划你的行程（可在任何一个城市开始），才能使得总收入（总营业额减去总交通费）最大？
输入
输入的第一行有两个整数T（1 <= T <= 100）和M（1 <= M <= 100），T代表总共的月数，M代表交通费。接下来的T行每行包括两个在1到100之间（包括1和100）的的整数，分别表示某个月在北京和在南京办公获得的营业额。
输出
输出只包括一行，这一行只包含一个整数，表示可以获得的最大总收入。
样例输入
4 3
10 9
2 8
9 5
8 2
1
2
3
4
5
样例输出
31
参考答案
//第二种方法
#include <bits/stdc++.h>
using namespace std;
int a[101],b[101]; //存储北京和南京每个月利润
int t,m;//t几个月，m路费
int suma[101],sumb[101],sum;
//suma【i】表示在北京第i个月办公获得最大利润
//sumb【i】表示在南京第i个月办公获得最大利润
int main(){
cin>>t>>m;//读入
for(int i=1;i<=t;i++){
cin>>a[i]>>b[i];
}
//计算
suma[1]=a[1];//在北京第一个月获得利润
sumb[1]=b[1];//在南京第一个月获得利润
for(int i=2;i<=t;i++){
suma[i]=max(suma[i-1]+a[i],sumb[i-1]+a[i]-m);//经过a[i],从北京或者南京来获得利润
sumb[i]=max(sumb[i-1]+b[i],suma[i-1]+b[i]-m);//经过b[i],从北京或者南京来获得利润
}
cout<<max(suma[t],sumb[t]);//输出
return 0;
}
上一题
下一题