游客 注册 | 登录
中文 | En

2276 - 城墙攻防战 wall(I)

通过次数

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

输出格式

60

C++解答

#include<iostream>
#include<algorithm>
using namespace std;
/*
6
3 1 6 4 5 2
60
*/
int sum(int a[],int start,int end){
	int s = 0;
	for(int i=start;i<end;i++){
		s+=a[i];
	}
	return s;
}

int minDigit(int a[],int start,int end){
	if((end-start)==1)
		return 1;
	else{
		int min = 999999999;
		for(int i=start;i<end;i++){
			if(min>a[i])
				min = a[i];
		}
		return min;
	}
}
int maxDigit(int a[],int len){
	int max = -999999999;
	for(int i=0;i<len;i++){
		for(int j=0,k=len-i;k<=len;j++,k++){
		
			int s = sum(a,j,k);
			int min = minDigit(a,j,k);
			s*=min;
			if(max<s)
				max = s;
			/*	
			for(int m=j;m<k;m++)
				cout<<a[m]<<" ";
			cout<<endl;
			cout<<minDigit(a,j,k)*sum(a,j,k)<<endl;	*/
		}
	}
	return max;
}
int main(){
	int n;
	while(cin>>n){
		int *a = new int[n];
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		cout<<maxDigit(a,n)<<endl;
	}
	return 0;
}

Java解答

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        while(in.hasNextInt()){
        int n=in.nextInt();
        int[] nn=new int[n];
        for(int i=0;i<nn.length;i++)
        nn[i]=in.nextInt();
          if(n==1) {System.out.println(nn[0]);continue;}
        int max=0,min,sum=0;
        for(int k=0;k<nn.length-1;k++){
            for(int j=k+1;j<nn.length;j++){
                 min=nn[k];
                 sum=min;
                 for(int h=k+1;h<=j;h++){
                     if(nn[h]<min) min=nn[h];
                     sum+=nn[h];
                    }
                    if(max<sum*min) max=sum*min;
                }
            }
             System.out.println(max);
            }
        }
    }
请先登陆