鏈接： https://www.nowcoder.com/acm/contest/121/C
來源：牛客網

時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 131072K，其他語言262144K
64bit IO Format: %lld

題目描述

????iko超級超級喜歡吃糖，有一天iko想出去玩，她計劃從1點走到N點（按1,2,3，...，n的順序走），每個點都有一個補給站，第i點的補給站有a[i]顆糖，從i點走到i+1點會消耗掉b[i]顆糖，iko在出游的途中可以選擇三個補給站，iko想知道她走完全程到達N點時口袋里最多還能剩下幾顆糖（初始時iko的口袋里一顆糖都沒有）。

輸入描述:

第一行輸入N（3<=N<=1000） 第二行輸入N個數代表a[1].......a[N] (0<=a[i]<=1000 ) 第三行輸入N-1個數代表b[1]......b[N-1] ( 1<=b[i]<=1000 )

輸出描述:

輸出一個數字表示iko到達n點時口袋里最多剩下的糖， 若不能到達N點輸出-1。示例1

輸入

3 1 3 4 3 4

輸出

-1示例2

輸入

5 3 4 5 2 4 3 2 2 2

輸出

3

解法1：

深度優先搜索 dfs

void dfs(int index,int sum,int cnt)

當前處于第index個補給站，口袋里有sum顆糖，還可以選擇cnt個補給站

初始時iko的口袋里一顆糖都沒有，所以sum=0；

若sum<0,說明無法到達下一個補給站

若當前處于最后一個補給站，如果還有補給機會，肯定要補給，如果沒有補給機會，則不補給

//dfs #include<bits/stdc++.h> using namespace std; const int maxn=1e3+5; int a[maxn];//補給 int b[maxn];//消耗 int n;//點的個數 int max_sum;//最多還能剩下幾顆糖 //index表示現在處于哪一個點，sum表示剩下幾顆糖，可以選擇cnt個補給站 void dfs(int index,int sum,int cnt) {if(sum<0)return ;if(index==n){//如果還有剩余的補給機會，肯定要補給，這樣才最多if(cnt>0&&sum+a[index]>max_sum)max_sum=sum+a[index];else if(cnt==0&&sum>max_sum)max_sum=sum;return ;}dfs(index+1,sum-b[index],cnt);//這一站不補給if(cnt>0)dfs(index+1,sum+a[index]-b[index],cnt-1);//這一站補給 } int main() {ios::sync_with_stdio(0);while(cin>>n){max_sum=-1;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<n;i++)cin>>b[i];dfs(1,0,3);//初始時iko的口袋里一顆糖都沒有cout<<max_sum<<endl; }return 0; }

解法2：

貪心

#include<bits/stdc++.h> using namespace std; const int maxn=1e3+5; int a[maxn];//補給 int b[maxn];//消耗 int n;//點的個數 int sum;//最多還能剩下幾顆糖 int main() {ios::sync_with_stdio(0);while(cin>>n){priority_queue<int> q;//每次取出最大int first;//第一個補給站int cnt=0;//補給次數cin>>first;q.push(first);//必須取第一個for(int i=1;i<n;i++)cin>>a[i];for(int i=1;i<n;i++)cin>>b[i];for(int i=1;i<n;i++){while(sum<b[i]&&!q.empty()){sum+=q.top();q.pop();cnt++;}sum-=b[i];if(sum<0){cnt=100;break;}q.push(a[i]);}while(!q.empty()&&cnt<3){sum+=q.top();q.pop();cnt++;}cout<<(cnt>3?-1:sum)<<endl; }return 0; }

總結

以上是生活随笔為你收集整理的陕西师范大学第七届程序设计竞赛 C题 iko和她的糖的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。