游客 注册 | 登录
中文 | En

2633 - 城墙攻防战 wall(II)

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

信科院的院长对于计科院学生称霸ACM平台一直很不爽，于是派出他们引以为豪的信科院ACM队来攻打计科院的城墙。这项防御任务自然就落到了计科院的ACM队的同学们身上。

已知计科院的城墙是由环形排列的N个石块组成，排列由1到N，每个石块都有它的防御值ai，由连续一段石块所组成城墙的防御值等于这一段城墙内所有石块防御值之和乘以这段城墙内防御最低的那块石头的防御值。

经过战术商讨，计科ACM队决定将敌人引入防御最高的一段城墙将其全歼，但是寻找出这段防御最高的城墙的问题需要他们快速解决。 


（注意这道题目的城墙是环形排列的，可以首尾连在一起）

题目输入

有多组数据，每组数据有两行

第一行一个正整数 N，表示城墙石块的个数。（N< 200)

第二行N个整数，表示每个石块的防御值ai。 (0<ai <=100)

题目输出

每行输出每一组最强防御的城墙的防御力。

输入/输出样例

输入格式

6
3 1 6 4 5 2
1
1

输出格式

60
1

C++解答

#include<iomanip>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
	int N,num;
	while(cin>>N){
		vector<int>v;
		while(N--){
			cin>>num;
			v.push_back(num);
		}
		int max=0;
		for(int i=v.size();i>0;i--){
			for(int j=0;j<v.size();j++){
				int sum=0;int min=101;
				for(int k=j,count=1;count<=i;k++,count++){
					if(k==v.size())
						k=0;
					sum+=v[k];
					if(min>v[k])
						min=v[k];
				}
				if(max<sum*min)
					max=sum*min;
			}	
		}
		cout<<max<<endl;
	}
	return 0;
}

Java解答

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		
		Scanner input = new Scanner(System.in);
		while(input.hasNextInt()){
			
			int N = input.nextInt();
			int[] ston = new int[N];
			int i,j;
			int defend = 0;
			
			for(i = 0; i < N; i++){
				
				ston[i] = input.nextInt();
			}
			
			int[] temp;
			for(i = 0; i < N; i++){
				
				for(j = 1; j <= N; j++){
					
					temp = new int[j];
					int sum = 0;
					for(int k = i,count = 0;count < j;k++,count++ ){
						
						int a = k >= N ? k - N : k;
						temp[count] = ston[a]; 
						sum += ston[a];
					}
					int min = min(temp);
					int tempDe = sum * min;
					if(defend < tempDe)
						defend = tempDe;
				}
			}
if(defend != 0)
			System.out.println(defend);
		}
	}
	
	public static int min(int[] arr){
		
		int min = arr[0];
		for(int i = 1; i < arr.length; i++){
			
			if(arr[i] < min)
				min = arr[i];
		}
		return min;
	}
}
请先登陆