2014
03-01

# Mystery ET

In the year 3890, we ALPCs find that the army of another planet is going to attack the earth, and we have to stop this attack to save our human beings, save the earth.
ALPC2587 has captured an ET, and he starts research this ET. Several days later he draws a conclusion that an ET’s living on the earth depends on a parameter named DR. DR measures the dangerousness of an ET. If an ET has a larger DR, it’s more dangerous. Now ALPCs have to find the maximum value of DR.
But there’s a problem that ET keeps growing: in an experience, first of all, we randomly put a cell of an ET in to box with N*N grids, every grid has a value, which is the value of DR (may be negative) of that grid. Then the cell grows freely and then constructs a creature. The creature’s DR is the total DR of all the girds it captured. In a unit time, the creature can choose one of its cell (grid) to grow to a adjacent grid.
Here’s an example:

ALPC2587 has experienced a lot but he is not clever enough to calculate the maximum DR, and all other ALPCs are busy with other tasks, so he comes to you for help. Please help him to calculate the maximum DR value the creature can gain in an experience.

There are multiple test cases, please process to the end of file.
In each the first line contains N (N<=9), the size of the box. Then comes N lines, each has N integers Aij (|Aij| < 32768), indicates the DR value of each grid.

There are multiple test cases, please process to the end of file.
In each the first line contains N (N<=9), the size of the box. Then comes N lines, each has N integers Aij (|Aij| < 32768), indicates the DR value of each grid.

4
2 -1 -1 -1
5 -5 -1 -5
3  2 -1  3
2 -2 -3  2

18

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

#define inf 0x7777777
#define int long long

using namespace std;
int const nMax = 500010;

int a[nMax];
int dp[nMax];
int sum[nMax];
int n,M;

int q[nMax],he,ta;
int dy(int i,int j){
return dp[i]+sum[i]*sum[i]-dp[j]-sum[j]*sum[j];
}
int dx(int i,int j){
return 2*(sum[i]-sum[j]);
}
void query(int i){
while(he<ta){
if(dy(q[he+1],q[he])<=sum[i]*(dx(q[he+1],q[he])))he++;
else break;
}
dp[i]=dp[q[he]]+(sum[i]-sum[q[he]])*(sum[i]-sum[q[he]])+M;
return ;
}
void insert(int i){
while(he<ta){
int y2=q[ta],y1=q[ta-1];
if(dy(y2,y1)*(dx(i,y2))>=dy(i,y2)*dx(y2,y1))ta--;
else break;
}
q[++ta]=i;
return ;
}

main()
{
while(~scanf("%I64d%I64d",&n,&M)){
sum[0]=0;
for(int i=1;i<=n;i++){
scanf("%I64d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
dp[0]=0;
ta=he=0;
q[0]=0;
int ans=inf;
for(int i=1;i<=n;i++){
query(i);
ans=min(ans,dp[i]);
insert(i);
}
printf("%I64d\n",dp[n]);
}
return 0;
}

1. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。