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

int n,l=0;
double f[2501];

struct node1
{
    int h,x,y;
}a[2501];

bool cmp1(node1 a,node1 b)
{
    return a.h>b.h;
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            scanf("%d",&a[++l].h);
            a[l].x=i;
            a[l].y=j;
        }
    sort(a+1,a+n*n+1,cmp1);
    memset(f,0,sizeof(f));
    for (int i=1;i<=l;i++)
        for (int j=1;j<i;j++)
            if (a[i].h<a[j].h)
                f[i]=max(f[i],f[j]+pow(double(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)),2));
    printf("%.0lf\n",f[l]);
}

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int d[3000],n,k,res;
struct nod{
int x,y,h;
}node[3000];
bool comp(nod a,nod b)
{
return a.h>b.h;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cin>>node[++k].h,node[k].x=i,node[k].y=j;
}
sort(node+1,node+n*n+1,comp);
for(int i=1;i<=n*n;i++){
for(int j=1;j<i;j++){
int h=(abs(node[i].x-node[j].x)+abs(node[i].y-node[j].y))*(abs(node[i].x-node[j].x)+abs(node[i].y-node[j].y));
if(node[i].h<node[j].h) d[i]=max(d[i],d[j]+h);
}
res=max(res,d[i]);
}
cout<<res;
return 0;
}

//话说还是记忆化搜索比较好写，但dp也不是不行
//dp的问题在于不知道更新的顺序，但这里可以看出先更新高的
//所以排个序就可以开始dp了
#include<iostream>
#include<algorithm>
using namespace std;
int map[60][60],dp[60][60];
struct node{
    int h,x,y;
}q[2510];
int cmp(const node&x,const node&y)
{
    return x.h>y.h;
}
int abss(int x)
{
    if(x>0)
     return x;
    else
     return -x;
}
int haha(int x)
{
    return x*x;
}
int main()
{
    int n,i,j,k,ans=0;
    cin>>n;
    for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
     {
        cin>>map[i][j];
        q[(i-1)*n+j].h=map[i][j];
        q[(i-1)*n+j].x=i;
        q[(i-1)*n+j].y=j;
     }
    sort(q+1,q+n*n+1,cmp);
    for(i=1;i<=n*n;i++)
    {
        for(j=1;j<=n;j++)
         for(k=1;k<=n;k++)
          if(q[i].h>map[j][k]) 
           dp[j][k]=max(dp[j][k],dp[q[i].x][q[i].y]+haha(abss(j-q[i].x)+abss(k-q[i].y)));
    }
    for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
      ans=max(ans,dp[i][j]);
    cout<<ans;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
struct aoligei{
int lao,ba,nb;
}a[100000];
int frog[100000];
bool yjh(aoligei g,aoligei h){
return g.lao>h.lao;
}
int main(){
int n,len=0;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[++len].lao;
a[len].ba=i;
a[len].nb=j;
}
}

sort(a+1,a+n*n+1,yjh);
for(int i=1;i<=n*n;i++){
for(int j=1;j<i;j++){
if(a[i].lao<a[j].lao)
frog[i]=max(frog[i],frog[j]+(abs(a[i].ba-a[j].ba)+abs(a[i].nb-a[j].nb))*(abs(a[i].ba-a[j].ba)+abs(a[i].nb-a[j].nb)));
}
}
cout<<frog[len];
return 0;
}

#include <bits/stdc++.h>
using namespace std;
struct ha{
int x,y,h;
}a[9999];
int f[100000];
int ans;
bool cmp(ha q, ha w){
return q.h>w.h;
}
int main(){
int n;
cin>>n;
int l=0;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
cin>>a[++l].h;
a[l].x=i;
a[l].y=j;
}
}
sort(a+1,a+n*n+1,cmp);
for(int i=1; i<=l; i++){
for(int j=1; j<i; j++){
if(a[i].h<a[j].h){
f[i]=max(f[i],f[j]+(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y))*(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)));
}
}
}
cout<<f[l];
return 0;
}#include <bits/stdc++.h>
using namespace std;
struct ha{
int x,y,h;
}a[9999];
int f[100000];
int ans;
bool cmp(ha q, ha w){
return q.h>w.h;
}
int main(){
int n;
cin>>n;
int l=0;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
cin>>a[++l].h;
a[l].x=i;
a[l].y=j;
}
}
sort(a+1,a+n*n+1,cmp);
for(int i=1; i<=l; i++){
for(int j=1; j<i; j++){
if(a[i].h<a[j].h){
f[i]=max(f[i],f[j]+(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y))*(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)));
}
}
}
cout<<f[l];
return 0;
}

//一定要这样，pow受限

所以为什么这道题是lis

n最大50,dp太麻烦,那就记忆化搜索吧。
var n,i,j:longint;
a:array[1..51,1..51]of longint;
f:array[1..51,1..51]of longint;
maxx,minx,maxy,miny,mx,mn:longint;
function max(a,b:longint):longint;
begin
 if a>b then max:=a else
 max:=b;
end;
function dfs(x,y:longint):longint;
var i,j:longint;
begin
 if f[x,y]<>-1 then exit(f[x,y]);
 for i:=1 to n do
 for j:=1 to n do
 if a[i,j]<a[x,y]then
 begin
  f[x,y]:=max(f[x,y],sqr(abs(x-i)+abs(y-j))+dfs(i,j));
 end;
 dfs:=f[x,y];
end;
begin
 mx:=-maxlongint;
 mn:=-mx;
 readln(n);
 for i:=1 to n do
 for j:=1 to n do
 begin
  read(a[i,j]);
  if mx<a[i,j]then
  begin
   mx:=a[i,j];
   maxx:=i;maxy:=j;
  end;
  if mn>a[i,j]then
  begin
   mn:=a[i,j];
   minx:=i;miny:=j;
  end;
 end;
 fillchar(f,sizeof(f),$ff);
 f[minx,miny]:=0;
 writeln(dfs(maxx,maxy));
end.

program p1474;
var a:array[0..5100] of integer;
x:array[0..5100] of integer;
y:array[0..5100] of integer;
f:array[0..5100] of longint;
i,j,k,m,n,s,ss,js,jh,max,sss:longint;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
begin
k:=(i-1)*n+j;
read(a[k]);
x[k]:=i;y[k]:=j;
end;
readln;
end;
m:=n*n;
for i:=1 to m-1 do
begin
for j:=i+1 to m do
begin
if a[i]>a[j] then
begin
jh:=a[i];
a[i]:=a[j];
a[j]:=jh;
jh:=x[i];
x[i]:=x[j];
x[j]:=jh;
jh:=y[i];
y[i]:=y[j];
y[j]:=jh;
end;
end;
end;
f[1]:=0;
for i:=2 to m do
begin
max:=0;
for j:=1 to i-1 do
begin
s:=abs(x[i]-x[j]);
ss:=abs(y[i]-y[j]);
sss:=sqr(ss+s);
if sss+f[j]>max then max:=sss+f[j];
end;
f[i]:=max;
end;
writeln(f[m]);
end.
AC了,恍恍惚惚恍恍惚惚恍恍惚惚

记录信息
评测状态 Accepted
题目 P1474 雷曼兔(csapc)
递交时间 2015-08-19 21:08:04
代码语言 C++
评测机 Jtwd2
消耗时间 75 ms
消耗内存 512 KiB
评测时间 2015-08-19 21:08:05
评测结果
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 504 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 504 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 504 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 508 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 512 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 504 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 508 KiB, score = 10
Accepted, time = 75 ms, mem = 512 KiB, score = 100
代码
#include <stdio.h>
#include <iostream>
#include <cmath>
using namespace std;
struct pos
{
int x,y,score;
};
pos here[2501];

int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int a;
scanf("%d",&a);
here[a].x=i;
here[a].y=j;
}
for(int i=n*n-1;i>=1;i--)
{
for(int j=i+1;j<=n*n;j++)
{
int p=(abs(here[i].x-here[j].x)+abs(here[i].y-here[j].y))*(abs(here[i].x-here[j].x)+abs(here[i].y-here[j].y));
if(p+here[j].score>here[i].score)
here[i].score=p+here[j].score;
}
}

printf("%d",here[1].score);
}

program p1598;
type
atype=record
x,y,data:longint;
end;
var n:longint;
map:array[0..3001]of atype;
f:array[0..3001]of longint;
procedure readin;
var i,j:longint;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(map[n*(i-1)+j].data);
map[n*(i-1)+j].x:=i;
map[n*(i-1)+j].y:=j;
end;
readln;
end;
end;
procedure swap(a,b:longint);
var t:atype;
begin
t:=map[a];
map[a]:=map[b];
map[b]:=t;
end;
procedure quicksort(l,r:longint);
var tl,tr,mid:longint;
begin
tl:=l;
tr:=r;
mid:=map[(l+r) div 2].data;
repeat
while map[tl].data>mid do inc(tl);
while map[tr].data<mid do dec(tr); if tl<=tr then begin swap(tl,tr); inc(tl); dec(tr); end; until tl>tr;
if l<tr then quicksort(l,tr);
if tl<r then quicksort(tl,r);
end;
procedure count;
var i,j,ans,p:longint;
begin
for i:=2 to n*n do
begin
ans:=0;
for j:=1 to i-1 do
begin
p:=f[j]+sqr(abs(map[i].x-map[j].x)+abs(map[i].y-map[j].y));
if ans<p then ans:=p; end; f[i]:=ans; end; ans:=0; for i:=1 to n*n do if f[i]>ans then
ans:=f[i];
writeln(ans);
end;
begin
readin;
quicksort(1,n*n);
count;
end.

#include<cstdio>
#include<cmath>
#define sz 2505
#define sqr(x) ((x)*(x))
using namespace std;
struct Type{
int x,y;
}a[sz];
int f[sz],n,p;
int main(){
//freopen("p1.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
scanf("%d",&p);
a[p].x=i;
a[p].y=j;
}
for(int i=sqr(n);i>=1;i--)
for(int j=1;j<=i;j++){
p=sqr(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y));
if (f[i]+p>f[j]) f[j]=p+f[i];
}
printf("%d",f[1]);
return 0;
}

#include<stdio.h>
#include<string.h>
int h[2500][2],v[2500];
int abs(int a)
{
if(a<0)return -a;
else return a;
}
int main()
{
int i,j,k,l,ans=0;
int n;
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&k);
k--;
h[k][0]=i;//横坐标
h[k][1]=j;//纵坐标
}
}
memset(v,0,sizeof(v));
for(i=n*n-1;i>=0;i--)
{
for(j=0;j<i;j++)
{
l=abs(h[i][0]-h[j][0])+abs(h[i][1]-h[j][1]);
l*=l;
if(v[i]+l>v[j])v[j]=v[i]+l;
}
if(v[i]>ans)ans=v[i];
}
printf("%d",ans);
return 0;
}
这题真的是LIS？？？

program exercise(input,output);
type atype=record
x,y,data:longint;
end;
var n:longint;
map:array[0..3001]of atype;
f:array[0..3001]of longint;
procedure readin;
var i,j:longint;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(map[n*(i-1)+j].data);
map[n*(i-1)+j].x:=i;
map[n*(i-1)+j].y:=j;
end;
readln;
end;
end;
procedure swap(a,b:longint);
var t:atype;
begin
t:=map[a];
map[a]:=map[b];
map[b]:=t;
end;
procedure quicksort(l,r:longint);
var tl,tr,mid:longint;
begin
tl:=l;
tr:=r;
mid:=map[(l+r) div 2].data;
repeat
while map[tl].data>mid do inc(tl);
while map[tr].data<mid do dec(tr);
if tl<=tr then
begin
swap(tl,tr);
inc(tl);
dec(tr);
end;
until tl>tr;
if l<tr then quicksort(l,tr);
if tl<r then quicksort(tl,r);
end;
procedure count;
var i,j,ans,p:longint;
begin
for i:=2 to n*n do
begin
ans:=0;
for j:=1 to i-1 do
begin
p:=f[j]+sqr(abs(map[i].x-map[j].x)+abs(map[i].y-map[j].y));
if ans<p then
ans:=p;
end;
f[i]:=ans;
end;
ans:=0;
for i:=1 to n*n do
if f[i]>ans then
ans:=f[i];
writeln(ans);
end;
begin
readin;
quicksort(1,n*n);
count;
end.

Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
Linking foo.exe
44 lines compiled, 0.1 sec , 29040 bytes code, 1628 bytes data
测试数据 #0: WrongAnswer, time = 0 ms, mem = 772 KiB, score = 0
测试数据 #1: WrongAnswer, time = 0 ms, mem = 772 KiB, score = 0
测试数据 #2: WrongAnswer, time = 0 ms, mem = 772 KiB, score = 0
测试数据 #3: WrongAnswer, time = 15 ms, mem = 772 KiB, score = 0
测试数据 #4: WrongAnswer, time = 15 ms, mem = 772 KiB, score = 0
测试数据 #5: WrongAnswer, time = 62 ms, mem = 768 KiB, score = 0
测试数据 #6: WrongAnswer, time = 171 ms, mem = 772 KiB, score = 0
测试数据 #7: WrongAnswer, time = 171 ms, mem = 764 KiB, score = 0
测试数据 #8: WrongAnswer, time = 156 ms, mem = 768 KiB, score = 0
测试数据 #9: WrongAnswer, time = 140 ms, mem = 772 KiB, score = 0
WrongAnswer, time = 730 ms, mem = 772 KiB, score = 0
代码
var
a,b,c,f:array[1..50,1..50]of longint;
n,ans,i,j,k,l,t:longint;
function max(i,j:longint):longint;
begin
if i>j then max:=i
else max:=j;
end;
function v(i,j,k,l:longint):longint;
begin
v:=sqr(abs(i-j)+(k-l));
end;

begin
readln(n);
for i:=1 to n do
for j:=1 to n do
begin
read(a[i,j]);
b[i,j]:=i;c[i,j]:=j;
end;
for i:=1 to n do
for j:=1 to n do
for k:=i+1 to n do
for l:=j+1 to n do
if a[i,j]<a[k,l]then
begin
t:=a[i,j];a[i,j]:=a[k,l];a[k,l]:=t;
t:=b[i,j];b[i,j]:=b[k,l];b[k,l]:=t;
t:=c[i,j];c[i,j]:=c[k,l];c[k,l]:=t;
end;
for i:=1 to n do
for j:=1 to n do
begin
f[i,j]:=0;
for k:=1 to n do
for l:=1 to n do
if a[i,j]>a[k,l]then f[i,j]:=max(f[i,j],f[k,l]+v(b[i,j],c[i,j],b[k,l],c[k,l]));
end;
ans:=0;
for i:=1 to n do
for j:=1 to n do
if f[i,j]>ans then ans:=f[i,j];
writeln(ans);
end.
为什么？！？！？！？！？！

AC 100 纪念～

#include <stdio.h>
#include <stdlib.h>
int dp[2500];
int sequence[2500][2];
int main(){
int size;
int i,k,temp;
scanf("%d",&size);
/* 接下来输入时把数据对应到 sequence 这个“桶”里，
即 sequence 的第 n-1 位存放高度为 n 的格子，[n-1][0] 存 x 坐标，[n-1][1] 存 y 坐标
(之所以不用第 n-1 位存放高度为 n 的格子，是因为 C 中的数组下标从 0 开始) */
for(i=0;i<size;i++){
for(k=0;k<size;k++){
scanf("%d",&temp);
temp--;
sequence[temp][0]=i;
sequence[temp][1]=k;
}
}
//DP数组清零
for(i=size*size-1;i>=0;i--)
dp[i]=0;
//从最高高度 (即 n^2-1)开始，直至高度为0
for(i=size*size-1;i>=0;i--){
for(k=0;k<i;k++){
//计算两点间华丽度
temp=abs(sequence[k][0]-sequence[i][0])+abs(sequence[k][1]-sequence[i][1]);
temp*=temp;
//如果现华丽度较原来大则更新
if(dp[i]+temp>dp[k])
dp[k]=dp[i]+temp;
}
}
printf("%d\n",dp[0]);
return 0;
}

太水了吧
begin
read(n);
for i:=1 to n do
for j:=1 to n do
read(a[i,j]);
for i:=1 to n do
for j:=1 to n do
begin
inc(m);b[m,1]:=i;b[m,2]:=j;b[m,3]:=a[i,j];
end;
n:=n*n;
dsort;
for i:=1 to n do
begin
j:=1;
while (j<i) do
begin
f[i]:=max(f[i],f[j]+sqr(abs(b[j,2]-b[i,2])+abs(b[j,1]-b[i,1])));
inc(j);
end;
end;
write(f[i]);
end.

这数据水到什么程度啊。。。。
我都只要1遍就AC了。。。。。

一遍A，不解释。
DXE

记忆化搜索就好了 1A!! O(∩_∩)O~
Var a,f:array[0..50,0..50] of longint;
x1,y1,x2,y2,n,i,j:longint;
Function max(a,b:longint):longint;
Begin
If a>b then exit(a) else exit(b);
End;
Function v(x1,y1,x2,y2:longint):longint;
Begin
exit(sqr(abs(x1-x2)+abs(y1-y2)));
End;
Function work(x,y:longint):longint;
Var i,j:longint;
Begin
work:=0;
If f[x,y]<>0 then exit(f[x,y]);
For i:=1 to n do
For j:=1 to n do
If a[i,j]<a[x,y] then
work:=max(work,work(i,j)+v(x,y,i,j));
F[x,y]:=work;
End;
Procedure main;
Var i,j,x1,x2,y1,y2,maxx,min:longint;
Begin
maxx:=0;
min:=maxlongint;
readln(n);
For i:=1 to n do
For j:=1 to n do
Begin
read(a[i,j]);
If a[i,j]>maxx then
begin
maxx:=a[i,j];
x1:=i;
y1:=j;
end;
If a[i,j]<min then
begin
min:=a[i,j];
x2:=i;
y2:=j;
end;
end;
F[x2,y2]:=0;
writeln(work(x1,y1));
End;
Begin
main;
readln;
End.
P.S：本人有强迫症=.=

AC80纪念~