NYOJ 955--我的，我的，都是我的！

我的，我的，都是我的！

1000 ms  |  内存限制：

65535

2

链接：

​​http://acm.nyist.net/JudgeOnline/problem.php?pid=955​​

念情发现了一些宝藏， 并且这些宝藏还是无穷无尽的！！念情正准备冲上去洗劫宝藏的时候，出来了一只护宝神兽

守护宝藏的神兽说：这里有N堆宝藏，他们都是无穷无尽的，你拿走之后，又会出现原来那么多的宝藏，不过你只能取连续的x堆宝藏，并且不能重复取连续的x堆宝藏。如果你这样做，所有的宝藏将消失。

念情很聪明，这点小问题不在话下，他完全能带走最多的宝藏，于是他大叫着：“我的！我的！都是我的！”，冲上去洗劫了一番。

现在告诉你每堆宝藏的宝藏数，你能知道念情这次得到了多少宝藏么？

Hint：

假设现在有三堆宝藏，每堆宝藏的宝藏数分别为 1  2  1

那么念情先取连续一堆： 1 + 2 + 1 = 4

再去连续两堆： （ 1 + 2 ） + （ 2 + 1 ）= 6

最后取连续三堆：（ 1 + 2 + 1 ）= 4

所以念情拿走的宝藏为 14

开始有一个整数T，表示T组测试数据

接下来每组开始一个N，表示有N堆宝藏

接下来一行有N个数，表示每堆宝藏的宝藏数

N<100,000

每堆宝藏的宝藏数<100,000

思路：

题意很清楚，简单的来说就是计算求和，

不过数据给的较大，直接做会超时，其实我们可以换一个思路：既然是每个元素都有取多次的结果，

不妨直接统计每个元素取的总次数，然后乘以该元素，最后累加.

参考代码:

/***************
Times:352ms
NYOJ 955
**************/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<string>
using namespace std;
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int n;
long long a[100001],b[100001],sum;
int main()
{
    int i,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        sum=0;
        mem(b,0);mem(a,0);
        for(i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }
        for(i=1; i<=n; i++)
        {
            b[i]=(a[i]*(n-i+1))*i;//计算每个元素取的总次数乘以其值赋给b数组
        }
       for(i=1; i<=n; i++)
            sum+=b[i];
        printf("%lld\n",sum);
    }
    return 0;
}      

换一种输入：

可优化：

参考代码：

（队友代码）

#include<stdio.h>
long long  shuru()
{
    long long  num=0;bool f=0;
    while(1)
    {
        char b=getchar();
        if(b=='-')
        {f=1;continue;}
        if(b==10||b==' ')
            return f==0?num:-num;
        num=num*10+(b-'0');
    }
}
long long  a;
int main()
{
    long long  n,T;
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld",&n);long long  x=0;getchar();
        long long  sum=0;
        long long f;
        long long xf=n;
        f=n-2;x=0;
        for(long long  i=0;i<n;i++)
        {
            a=shuru();
            sum+=a*xf;
            if(!x&&f<0) x=1;
            xf=xf+f;
            f-=2;
        }
        printf("%lld\n",sum);
    }
}