采木-C++

 采木-题目描述

在你面前依次排着n棵树，而你有两种工具，锯子和斧头，它们砍第i棵树的时间分别为ai和bi，一开始你拿的是斧头，而砍第i棵树前交换工具需要花费ci的时间，问题来了，依次砍2完这些树的时间最短为多少呢？

输入输出

输入

第一行一个数n（n<=100）
接下来n行，每行3个数ai，bi，ci（<=30000）

输出

一个数最短时间

样例

输入

3
20 40 20
10 4 25
90 100 5

输出

139

注：没参加答题，不知道通过多少测试用例，我的方法是从后往前找，目前我写的测试用例输出都是最小，此方法还是优于暴力解法的

#include "stdafx.h"
#include
#include
#include
using namespace std;
int main()
{int n;cin >> n;int a, b, c,min=0;int flag = 0;//初始为0，为锯子vector ft, jz, ct;//int ft[100], jz[100], ct[100];for (int i = 0; i < n; i++){cin >> a >> b >> c;//cin >>ft[i]>>jz[i]>>ct[i];jz.push_back(a);//锯子ft.push_back(b);//斧头ct.push_back(c);}if (ft[n - 1] > jz[n - 1])min += jz[n - 1];else{min += ft[n - 1];flag = 1;//1为斧头}for (int i = n - 2; i > 0; i--){if ((ft[i] < jz[i]) && flag ==1)//上一轮为斧头，这一轮斧头继续小，不需要切换min += ft[i];else if ((ft[i] < jz[i]) && flag ==0)//上一轮为锯子,这一轮斧头小，看是否需要切换{if (ft[i] + ct[i + 1] < jz[i]){min += ft[i] + ct[i + 1];flag = 1;}elsemin +=jz[i];}else if ((ft[i] > jz[i]) && flag ==0)//上一轮为锯子，这一轮锯子继续小，不需要切换min +=jz[i];else //((ft[i] >jz[i]) && flag = 1)//上一轮的为斧头，这一轮锯子小，需要判定需要切换不{if (jz[i] + ct[i + 1] < ft[i]){min += jz[i] + ct[i + 1];flag = 0;}elsemin +=ft[i];}}if (flag == 0)//锯子min += (ft[0] + ct[1]);elsemin += ft[0];cout << "min=" << min <

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！