試題 A: 數(shù)青蛙

“一只青蛙一張嘴，兩只眼睛四條腿」匣青蛙兩張嘴，四只眼睛八條腿。三只青蛙三張嘴，六只眼睛十二條腿。……二十只青蛙二十張嘴，四十只眼睛八十條腿?！?/p>

請問膳綾擎這段文字，如不雅完全不省略，全部寫出來，大年夜 1 到 20 只青蛙，總共有若干個漢字。

商定：數(shù)字 2 零丁出現(xiàn)讀成 “兩”，在其他數(shù)瑯綾擎讀成 “二”，例如 “十二”。10 讀作 “十”，11 讀作 “十一”，22 讀作 “二十二”。請只計(jì)算漢字的個數(shù)，標(biāo)點(diǎn)符號不計(jì)算。

謎底353

上限20只青蛙,腿最多80只,所以只須要推敲1~80的漢字個數(shù)即可.

個位數(shù)一位;11~19以及10的倍數(shù)兩位;其余情況三位

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
int n(int x){
	if(x<=10) return 1;
	if(x%10==0) return 2;
	if(x<20) return 2;
	return 3;
}
int main(){
	int sum = 0;
	for(int i = 1 ; i <=20 ; i ++){
		int a = i;
		int b = i + i;
		int c = i *4;
		sum += 10;
		sum += n(a)*2;
		sum+=n(b) + n(c);
	}
	cout<<sum<<endl;
	return 0;
}

試題 B: 互質(zhì)

本年是 2020 年，今天是 10 月 18 日。
請問在 1 到 2020 中，有若干個數(shù)與 1018 互質(zhì)。

謎底:1008

因?yàn)槭翘羁疹},所以不須要推敲什么算法,直接暴力試就可

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;

int gcd2(int a,int b){
	return b==0?a:gcd(b,a%b);
}
int main(){
	int sum = 0;
	for(int i = 1 ; i <= 2020; i ++){
		if(gcd2(1018,i) == 1){
			sum ++;
		}
	}
	cout<< sum <<endl;
	return 0;
}

試題 C: 車牌

A 市的車牌由六位構(gòu)成，個中前三位可能為數(shù)字 0 至 9，或者字母 A 至 F，每位有 16 種可能。后三位只能是數(shù)字 0 至 9。為了削減攀比，車牌中不克不及有持續(xù)三位是雷同的字符。

例如，202020 是合法的車牌，AAA202 不是合法的車牌，因?yàn)榍叭齻€字母雷同。

請問，A 市有若干個合法的車牌？

謎底:3997440

---

總共情況為16*16*16*10*10*10

第一位第二位第三位字符一致,可以看做一位,有16種情況,第四位第五位第六位分別有10種情況

第一位16種情況,第二位第三位第四位一致,看做一位,有10種情況,第五位第六位分別有10種情況

第一位16種情況,第二位16種情況,第三第四第五位一致看做一位,有10種情況,第六位10種情況

第一位第二位第三位分別16種情況,第四位第五位第六位一致,看做一位,有10種情況

采取正難則反的思惟,總數(shù)減去清除情況數(shù),就是謎底

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;

int main(){
	int sum = 16*16*16*10*10*10;
	sum -= 16*10*10*10;
	sum -= 16*10*10*10;
	sum -= 16*16*10*10;
	sum -= 16*16*16*10;
	cout<<sum<<endl;
	return 0;
}

試題 D: Fibonacci 集合

小藍(lán)定義了一個 Fibonacci 集合 F，集合的元素如下定義：

1. 最小的 5 個 Fibonacci 數(shù) 1, 2, 3, 5, 8 屬于集合 F。

2. 如不雅一個元素 x 屬于 F，則 3x + 2、5x + 3 和 8x + 5 都屬于集合 F。

3. 其他元素都不屬于 F。

請問，這個集合中的第 2020 小元素的值是若干？

謎底 41269

標(biāo)準(zhǔn)深搜題,數(shù)字請求也不大年夜,暴力即可

大年夜最小的五個數(shù)開端搜刮,把搜刮到的數(shù)字置一,然后再找地2020個置一的數(shù)字即可

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
int fx[100010];
bool is[100010];
void dfs(int n){
	if(n > 100000) return ;
	is[n] = true;
	dfs(n*3+2);
	dfs(n*5+3);
	dfs(n*8+5);
}
int main(){
	dfs(1);
	dfs(2);
	dfs(3);
	dfs(5);
	dfs(8);
	int sum = 0;
	for(int i = 1;i<=100010;i++){
		if(is[i]){
			sum ++;
			cout<< sum << " ge  = " << i<<endl;
			if(sum == 2020){
				break;
			}
		}
	}
	return 0;
}

試題 E: 上升子串

小藍(lán)有一個字母矩陣，他愛好和小伙伴們在這個矩陣上玩一些游戲。今天，他計(jì)算玩找上升子串的游戲。游戲是合作性質(zhì)的。小藍(lán)和小伙伴們起重要在矩陣中指定一個地位，然后大年夜這個地位開端，向高低閣下相鄰地位移動，移動必須知足所達(dá)到地位上的字母比當(dāng)前地位大年夜。小藍(lán)和小伙伴們可以移動隨便率性多次，也可以隨時停下來，如許就找到了一個上升子串。只要子串在矩陣中的地位不合，就認(rèn)為是不合的子串。

小藍(lán)想知道，一共可以找到若干個上升子串。小藍(lán)的矩陣很大年夜，已經(jīng)放在了試標(biāo)題次下面，叫 inc.txt。為了更清跋扈的

描述問題，他還找了一個很小的矩陣用來解釋。

例如，對于矩陣：

AB
BC

可以找到 4 個長度為 1 的上升子串、4 個長度為 2 的上升子串、2 個長度

為 3 的上升子串，共 10 個。

如今，請你對于小藍(lán)的大年夜矩陣，找到上升子串的數(shù)量。

謎底未知

這題暴力過不去,比賽的時刻跑了兩個多小時,還在跑......

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<queue>
using namespace std;
char a[102][102];
int sum;
struct mu{
	int x;
	int y;
	char maxChar;
	mu(int xx,int yy,char z){
		x = xx;
		y = yy;
		maxChar = z;
	}
};
bool check(int x){
	if(x<0 || x >= 100) return false;
	return true;
}
void bfs(int x,int y){
	queue<mu> q;
	q.push(mu(x,y,a[x][y]));
	while(!q.empty()){
		mu mm = q.front();
		sum ++;
		cout<<sum<<endl;
		q.pop();
		if(check(mm.x - 1) && mm.maxChar < a[mm.x - 1][mm.y]){
			mu m2 = mu(mm.x - 1,mm.y,a[mm.x - 1][mm.y]);
			q.push(m2);
		}
		if(check(mm.x + 1) && mm.maxChar < a[mm.x + 1][mm.y]){
			mu m3 = mu(mm.x + 1,mm.y,a[mm.x + 1][mm.y]);
			q.push(m3);
		}
		if(check(mm.y + 1) && mm.maxChar < a[mm.x][mm.y + 1]){
			mu m4 = mu(mm.x,mm.y + 1,a[mm.x][mm.y + 1]);
			q.push(m4);
		}
		if(check(mm.y - 1) && mm.maxChar < a[mm.x][mm.y - 1]){
			mu m5 = mu(mm.x,mm.y - 1,a[mm.x][mm.y - 1]);
			q.push(m5);
		}
	}
}
int main(){
	sum = 0;
	for(int i = 0 ; i < 100;i++){
		cin>>a[i];
	}
	for(int i = 0 ; i < 100;i++){
		for(int j = 0 ; j < 100 ; j ++){
			bfs(i,j);
		}
	}
	cout<<sum<<endl;
	return 0;
}

試題 F: 日期辨認(rèn)

小藍(lán)要處理異常多的數(shù)據(jù)，個中有一些數(shù)據(jù)是日期。在小藍(lán)處理的日期中有兩種常用的情勢：英文情勢和數(shù)字情勢。英文情勢采取每個月的英文的前三個字母作為月份標(biāo)識，后面跟兩位數(shù)字表示日期，月份標(biāo)識第一個字母大年夜寫，后兩個字母小寫，日孚小于 10 時要補(bǔ)前導(dǎo) 0。1 月到 12 月英文的前三個字母分別是 Jan、Feb、Mar、Apr、May、Jun、Jul、Aug、Sep、Oct、Nov、Dec。數(shù)字情勢直接用兩個整數(shù)表達(dá)，中心用一個空格分隔，兩個整數(shù)都不寫前導(dǎo) 0。個中月份用 1 至 12 分別表示 1 月到 12 月。

輸入一個日期的英文情勢，請輸出它的數(shù)字情勢。

【樣例輸入】
Feb08
【樣例輸出】
2 8
【樣例輸入】
Oct18
【樣例輸出】
10 18

話不多說,暴力

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
void run(string s){
	if(s[0] == 'J' && s[1] == 'a' && s[2] == 'n'){
		printf("1 ");
	}
	else if(s[0] == 'F' && s[1] == 'e' && s[2] == 'b'){
		printf("2 ");
	}
	else if(s[0] == 'M' && s[1] == 'a' && s[2] == 'r'){
		printf("3 ");
	}
	else if(s[0] == 'A' && s[1] == 'p' && s[2] == 'r'){
		printf("4 ");
	}
	else if(s[0] == 'M' && s[1] == 'a' && s[2] == 'y'){
		printf("5 ");
	}
	else if(s[0] == 'J' && s[1] == 'u' && s[2] == 'n'){
		printf("6 ");
	}
	else if(s[0] == 'J' && s[1] == 'u' && s[2] == 'l'){
		printf("7 ");
	}
	else if(s[0] == 'A' && s[1] == 'u' && s[2] == 'g'){
		printf("8 ");
	}
	else if(s[0] == 'S' && s[1] == 'e' && s[2] == 'p'){
		printf("9 ");
	}
	else if(s[0] == 'O' && s[1] == 'c' && s[2] == 't'){
		printf("10 ");
	}
	else if(s[0] == 'N' && s[1] == 'o' && s[2] == 'v'){
		printf("11 ");
	}
	else if(s[0] == 'D' && s[1] == 'e' && s[2] == 'c'){
		printf("12 ");
	}
	if(s[3] != '0'){
		cout<<s[3];
	}
	cout<<s[4]<<endl;
}
int main(){
	string str;
	while(cin>>str){
		run(str);
	}
	return 0;
}

試題 G: 乘法表

九九乘法表是進(jìn)修乘法時必須要控制的。在不合進(jìn)制數(shù)下，須要不合的乘
法表。
例如，四進(jìn)制下的乘法表如下所示：

1*1=1
2*1=2 2*2=10
3*1=3 3*2=12 3*3=21

請留意，乘法表中兩個數(shù)相乘的次序必須為樣例中所示的次序，不克不及隨便
交換兩個乘數(shù)。
給定 P，請輸出 P 進(jìn)制下的乘法表。

【輸入格局】
輸入一個整數(shù) P。
【輸出格局】
輸出 P 進(jìn)制下的乘法表。P 進(jìn)制中大年夜于等于 10 的數(shù)字用大年夜寫字母 A、B、 C、· · · 表示。
【樣例輸入】
4
【樣例輸出】
1*1=1
2*1=2 2*2=10
3*1=3 3*2=12 3*3=21

【樣例輸入】
8
【樣例輸出】
1*1=1
2*1=2 2*2=4
3*1=3 3*2=6 3*3=11
4*1=4 4*2=10 4*3=14 4*4=20
5*1=5 5*2=12 5*3=17 5*4=24 5*5=31
6*1=6 6*2=14 6*3=22 6*4=30 6*5=36 6*6=44
7*1=7 7*2=16 7*3=25 7*4=34 7*5=43 7*6=52 7*7=61

【評測用例范圍與商定】

對于所有評測數(shù)據(jù)，2 ≤ P ≤ 36。

應(yīng)用棧進(jìn)行進(jìn)制轉(zhuǎn)換即可,留意10以長進(jìn)制的須要輸出字符A-F

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<stack>
using namespace std;
void printNum(int num,int p){
	stack<int> s;
	while(num>0){
		s.push(num%p);
		num/=p;
	}
	while(!s.empty()){
		if(s.top() > 9){
			printf("%c",'A'+ s.top() - 10);
		}
		else{
			cout<<s.top();
		}
		s.pop();
	}
}
void run(int p){
	for(int i = 1 ; i < p ; i ++){
		for(int j = 1;j <= i;j ++){
			int sum = i * j;
			if(j!=1){
				printf(" ");
			}
			if(i > 9){
				printf("%c",'A'+i-10);
			}else{
				printf("%d", i);
			}
			printf("*");
			if(j > 9){
				printf("%c",'A'+j-10);
			}else{
				printf("%d", j);
			}
			printf("=");
			printNum(sum,p);
		}
		printf("\n");
	}
}
int main(){
	int p;
	while(cin>>p){
		run(p);
	}
	return 0;
}

試題 H: 限高桿

【問題描述】

某市有 n 個路口，有 m 段門路連接這些路口，構(gòu)成了該市的公路體系。個一一段門路兩端必定連接兩個不合的路口。門路中心不會穿過路口。因?yàn)楦黝愒?#xff0c;在一部分門路的中心設(shè)置了一些限高桿，有限高桿的路段貨車無法經(jīng)由過程。在該市有兩個重要的市場 A 和 B，分別在路口 1 和 n 鄰近，貨車大年夜市場 A出發(fā)，起首走到路口 1 ，然后經(jīng)由公路體系走到路口 n，才能達(dá)到市場 B。

兩個市場異常繁華，天天有很多貨車往返于兩個市場之間。市長發(fā)明，因?yàn)橄薷邨U很多，導(dǎo)致貨車可能須要繞行才能往返于市場之間，這使得貨車袈溱公路體系中的行駛路程變長，增長了對公路體系的損耗，增長了能源的消費(fèi)，同時還增長了情況污染。市長決定要將兩段門路中的限高桿拆除，使得市場 A 和市場 B 之間的路程變短。請問最多能削減多長的距離？

【輸入格局】

輸入的第一行包含兩個整數(shù) n, m，分別表示路口的數(shù)量和門路的段數(shù)。
接下來 m 行，每行四個整數(shù) a, b, c, d，表示路口 a 和路口 b 之間有一段長度為 c 的門路。如不雅 d 為 0，表示這段門路膳綾腔有限高桿；如不雅 d 為 1，表示這段門路上有限高桿。兩個路口之間可能有多段門路。
輸入數(shù)據(jù)包管在不拆除限高桿的情況下，貨車能經(jīng)由過程公路體系大年夜路口 1 正常行駛到路口 n。

【輸出格局】
輸出一行，包含一個整數(shù)，表示拆除兩段門路的限高桿后，市場 A 和市場B 之間的路程最大年夜削減多長距離。

【樣例輸入】
5 7
1 2 1 0
2 3 2 1
1 3 9 0
5 3 8 0
4 3 5 1
4 3 9 0
4 5 4 0
【樣例輸出】
6

【樣例解釋】

只有兩段門路有限高桿，全部拆除后，1 到 n 的路程由本來的 17 變?yōu)榱?br /> 11，削減了 6。

【評測用例范圍與商定】

對于 30% 的評測樣例，2 ≤ n ≤ 10，1 ≤ m ≤ 20, 1 ≤ c ≤ 100。
對于 50% 的評測樣例，2 ≤ n ≤ 100，1 ≤ m ≤ 1000, 1 ≤ c ≤ 1000。
對于 70% 的評測樣例，2 ≤ n ≤ 1000，1 ≤ m ≤ 10000, 1 ≤ c ≤ 10000。
對于所有評測樣例，2 ≤ n ≤ 10000，2 ≤ m ≤ 100000, 1 ≤ c ≤ 10000，至少
有兩段門路有限高桿。

先計(jì)算不拆限高架的情況下,即d等于1的輸入數(shù)據(jù),我們先保存起來,個中g(shù)anx保存起點(diǎn),gany保存終點(diǎn),ganLi保存距離

因?yàn)樗{(lán)橋杯是閉卷測驗(yàn),dijkstra算法一會兒想不起來了,所以應(yīng)用了floyd算法,暴力三層for輪回,找到每個點(diǎn)之間的最短路徑保存在li1數(shù)組中,把1到n的最短路徑保存在 qianAns 中

然后再兩層for輪回遍歷限高的門路,應(yīng)用li2臨時數(shù)組復(fù)制li1的最短路數(shù)據(jù),然后測驗(yàn)測驗(yàn)把兩個拆掉落限高的路加進(jìn)去,再求一遍最短路

多次遍歷完成,計(jì)算出最短值

相減就是謎底,算法異常差,但基本樣例可以過

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<queue>
using namespace std;
int li1[10002][10002]; // qian
int li2[10002][10002]; // hou
int ganx[10002];
int gany[10002];
int ganLi[10002];
int main(){
	
	int n,m;
	
	while(cin>>n>>m){
		memset(li1,1,sizeof(li1));
		int ganGe = 0;
		for(int i = 0 ; i <= n ; i ++){
			li1[i][i] = 0;
		}
		for(int i = 0 ; i < m ; i ++){
			int a,b,c,d;
			scanf("%d%d%d%d",&a,&b,&c,&d);
			if(d == 0){
				if(li1[a][b] > c){
					li1[a][b] = c;
				}
				if(li1[b][a] > c){
					li1[b][a] = c;
				}
			}else{
				ganx[ganGe] = a;
				gany[ganGe] = b;
				ganLi[ganGe++] = c;
			}
		}
		for(int i = 1 ; i <= n ; i ++ ){
			for(int j = 1 ; j <= n ; j++ ){
				for(int k = 1 ; k <= n ; k ++ ){
					if(li1[i][j] > li1[i][k] + li1[k][j] ){
						li1[i][j] = li1[i][k] + li1[k][j];
					}
				}
			}
		}
		int qianAns = li1[1][n];
		int houAns = 99999;
		for(int g1 = 0 ; g1<ganGe ; g1 ++ ){
			for(int g2 = g1 + 1 ; g2 < ganGe ; g2++){
				for(int i = 1;i<=n;i++){
					for(int j = 1 ; j <= n ; j ++){
						li2[i][j] = li1[i][j];
					}
				}
				if(li2[ganx[g1]][gany[g1]] > ganLi[g1]){
					li2[ganx[g1]][gany[g1]] = ganLi[g1];
				}
				if(li2[gany[g1]][ganx[g1]] > ganLi[g1]){
					li2[gany[g1]][ganx[g1]] = ganLi[g1];
				}
				if(li2[ganx[g2]][gany[g2]] > ganLi[g2]){
					li2[ganx[g2]][gany[g2]] = ganLi[g2];
				}
				if(li2[gany[g2]][ganx[g2]] > ganLi[g2]){
					li2[gany[g2]][ganx[g2]] = ganLi[g2];
				}
				for(int i = 1 ; i <= n ; i ++ ){
					for(int j = 1 ; j <= n ; j++ ){
						for(int k = 1 ; k <= n ; k ++ ){
							if(li2[i][j] > li2[i][k] + li2[k][j] ){
								li2[i][j] = li2[i][k] + li2[k][j];
							}
						}
					}
				}
				if(li2[1][n] < houAns){
					houAns = li2[1][n];
				}
			}
		}
		
		// cout<<qianAns << endl;
		// cout<<houAns<<endl;
		cout<<qianAns - houAns<<endl;
	}
	return 0;
}

試題 I: 畫中漂流

【問題描述】

在夢境中，你踏上了一只木筏，在江上漂流。根據(jù)對本地的懂得，你知道在你下流 D 米處有一個峽谷，如不雅你向下流前
進(jìn)大年夜于等于 D 米則必逝世無疑。如今你打響了急救德律風(fēng)，T 秒后救濟(jì)隊(duì)會達(dá)到并將你救上岸。水流速度是1 m/s，你如今有 M 點(diǎn)體力。每消費(fèi)一點(diǎn)體力，你可以整潔秒槳使船向上游進(jìn)步 1m，不然會向下流進(jìn)步 1m (水流)。M 點(diǎn)體力需在救濟(jì)隊(duì)趕來前花光。因?yàn)榻嫣珜捔?#xff0c;憑借你本身的力量弗成能上岸。請問，有若干種劃槳的籌劃可以讓你得救。

兩個劃槳籌劃不合是指：存在某一秒鐘，一個籌劃劃槳，另一個籌劃不劃。

【輸入格局】

輸入一行包含三個整數(shù) D, T, M。

【輸出格局】
輸出一個整數(shù)，表示可以讓你得救的總籌劃數(shù)，謎底可能很大年夜，請輸出方
案數(shù)除以 1, 000, 000, 007 的余數(shù)。

【樣例輸入】
1 6 3
【樣例輸出】
5

【評測用例范圍與商定】

對于 50% 的評測用例，1 ≤ T ≤ 350。
對于所有評測用例，1 ≤ T ≤ 3000, 1 ≤ D ≤ T, 1 ≤ M ≤ 1500。

我應(yīng)用了廣搜,構(gòu)造體的weizhi是相對于起點(diǎn)的地位,tili為當(dāng)前還剩下的體力,time是當(dāng)前殘剩的時光

留意標(biāo)題請求,必須在救濟(jì)隊(duì)來之前把體力用完,如不雅沒用完,不計(jì)數(shù)

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<queue>
using namespace std;
struct mu{
	int weizhi;
	int tili;
	int time;
	mu(int x,int y,int z){
		weizhi = x;
		tili = y;
		time = z;
	}
};
void bfs(int d,int t,int m){
	int ans = 0;
	d = -d;
	queue<mu> q;
	q.push(mu(0,m,t));
	while(!q.empty()){
		mu mm = q.front();
		if(mm.weizhi <= d){ // si
			q.pop();
			continue;
		}
		if(mm.tili == 0 && mm.time == 0){
			ans ++;
		}
		if(mm.time <= 0){
			q.pop();
			continue;
		}
		if(mm.tili > 0){ // up
			mu m1 = mu(mm.weizhi + 1,mm.tili -1 , mm.time - 1);
			q.push(m1);
		}
		// down
		mu m2 = mu(mm.weizhi - 1,mm.tili , mm.time - 1);
		q.push(m2);
		q.pop();
	}
	cout<<ans<<endl;
}
int main(){
	int d,t,m;
	while(cin>>d>>t>>m){
		bfs(d,t,m);
	}
	return 0;
}

試題 J: 觀光家

【問題描述】

早年，在海上有 n 個島嶼，編號 1 至 n。居平易近們深受洋流困擾，無法達(dá)到比本身當(dāng)前地點(diǎn)島嶼編號更小的島嶼。經(jīng)由數(shù)年今后，島嶼上的人數(shù)跟著島嶼的編號遞增（可能相等）。作為一名出色的觀光家（RP 學(xué)家），你想大年夜 1 號島嶼出發(fā)開啟一次路程，以獲得更多的 RP，因?yàn)槭艿胶Ｑ蟮难罅饔绊?#xff0c;你只能去到比當(dāng)前島嶼編號更大年夜的島嶼。因?yàn)槟惚容^仁慈，你會在分開一個島嶼的時刻將你的 RP 分散給島平易近，具體的：你的 RP 會除以 2（用去尾法取整，或者說向零取整）（當(dāng)你的 RP 小于零時，島平易近也依舊要幫你分擔(dān)，畢竟你們已經(jīng)建立起了深摯的友情）。第 i 號島嶼有 Ti 人, 然則你很抉剔，每次你大年夜 j 號島嶼達(dá)到 i 號島嶼時，你只會在達(dá)到的島嶼上做 Ti × T j 件功德（一件功德可以獲得 1 點(diǎn) RP)。

獨(dú)一不足的是，因?yàn)槟阍趰u上住宿，勞平易近傷財(cái)，你會扣除巨量 RP，第 i 號島嶼的住宿扣除 Fi 點(diǎn) RP。留意：將分開一個島嶼時，先將 RP 扣除一半，再扣除住宿的 RP，最后在新達(dá)到的島嶼上做功德，增長 RP。分開 1 號島嶼時須要扣除在 1 號島嶼住宿的 RP，當(dāng)達(dá)到這段路程的最后一個島嶼上時，要做完功德，行程才能爭止，也就是說不消扣除在最后達(dá)到的島嶼上住宿的 RP。你因?yàn)榭釔塾^光 (RP)，所以大年夜 1 號島嶼開端觀光，初始時你有 0 點(diǎn) RP。

你欲望選擇一些島嶼經(jīng)由，最終選擇一個島嶼停下來，求最大年夜的 RP 值是若干？

【輸入格局】

輸入的第一行包含一個數(shù) n , 表示島嶼的總數(shù)。

第二行包含 n 個整數(shù) T1, T2, · · · , Tn , 表示每個島嶼的人口數(shù)。

第三行包含 n 個整數(shù) F1, F2, · · · , Fn , 表示每個島嶼旅店損掉的 RP。

【輸出格局】

輸出一個數(shù)，表示最大年夜獲得的 RP 值。

【樣例輸入】
3
4 4 5
1 10 3
【樣例輸出】
19

【樣例解釋】

大年夜一號島嶼直接走到三號島嶼最優(yōu)，初始 0 點(diǎn) RP，扣除一半取整變成 0點(diǎn)?？鄢谝惶柟?jié)點(diǎn)住宿的 1 RP，在三號島嶼做功德產(chǎn)生 4 × 5 = 20 點(diǎn) RP,最終獲得 19 點(diǎn) RP。

【樣例輸入】
5
969 980 1013 1016 1021
888423 945460 865822 896150 946615
【樣例輸出】
246172

【評測用例范圍與商定】

對于 20% 的評測用例，1 ≤ n ≤ 15；
對于 70% 的評測用例，1 ≤ n ≤ 5000；
對于所有評測用例，1 ≤ n ≤ 500000, 1 ≤ Ti ≤ 20000, 1 ≤ Fi ≤ 200, 000, 000。
給定的 Ti 已經(jīng)按照升序排序。建議應(yīng)用 64 位有符號整數(shù)進(jìn)交運(yùn)算。

我是完全模仿標(biāo)題標(biāo)思路寫得代碼,留意n等于1的時刻須要特判

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<queue>
using namespace std;
long long a[500010];
long long b[500010];
int n;
long long maxRp;
void dfs(long long rp,int index,long long qianRen){
	// ting
	if(index +1 > n) return ;
	if(rp + qianRen * a[index + 1] > maxRp){
		maxRp = rp + qianRen * a[index + 1];
	}
	dfs((rp + qianRen * a[index + 1])/2 - b[index + 1],index + 1,a[index + 1]);
	//buting
	dfs(rp,index+1,qianRen);
}
int main(){
	while(cin>>n){
		
		for(int i = 1 ; i <= n ; i ++){
			scanf("%lld",&a[i]);
		}
		for(int i = 1 ; i <= n ; i ++){
			scanf("%lld",&b[i]);
		}
		if(n == 1) {
			cout<<"0"<<endl;
		}else{
			maxRp = -b[1];
			dfs(-b[1],1,a[1]);
			cout << maxRp << endl;
		}
	}
	return 0;
}