Problem:2853 新建题解

Solution_ID:21968            。。

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,a[200][200],dp[200][200][400];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	} 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=2*n;k++)
				dp[i][j][k]=-2147483640;
	dp[1][1][2]=0; 
	for(int k=3;k<=2*n;k++){
		for(int j=1;j<=n;j++){
			for(int i=1;i<=n;i++){
				if(k-i>n || k-j>n) continue;
				if(k-i<1 || k-j<1) break; 
				else dp[i][j][k]=max(max(dp[i-1][j][k-1],dp[i][j][k-1]),max(dp[i][j-1][k                                                       -1],dp[i-1][j-1][k-1]))+abs(a[i][k-i]-a[j][k-j]);
			}
		}
	}
	cout<<dp[n][n][2*n];
}

by 30993 十月 6, 2016, 9:14 p.m.

Solution_ID:21967            。。

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

int n,a[200][200],dp[200][200][400];

int main(){

cin>>n;

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

cin>>a[i][j];

}

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

for(int k=1;k<=2*n;k++)

dp[i][j][k]=-2147483640;

dp[1][1][2]=0; 

for(int k=3;k<=2*n;k++){

for(int j=1;j<=n;j++){

for(int i=1;i<=n;i++){

if(k-i>n || k-j>n) continue;

if(k-i<1 || k-j<1) break; 

else dp[i][j][k]=max(max(dp[i-1][j][k-1],dp[i][j][k-1]),max(dp[i][j-1][k-1],dp[i-1][j-1][k-1]))+abs(a[i][k-i]-a[j][k-j]);

}

}

}

/*for(int k=3;k<=2*n;k++)

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

cout<<i<<" "<<k-i<<" "<<j<<" "<<k-j<<" "<<dp[i][j][k]<<endl;*/

cout<<dp[n][n][2*n];

}


by 30993 十月 6, 2016, 9:10 p.m.

Solution_ID:20310            真MZOI交警大队长

                   时间复杂度:Θ() 空间复杂度:Θ()

自己看楼下题解


by 42115 八月 3, 2016, 4:56 p.m.

Solution_ID:20304            我要吐槽

                   时间复杂度:Θ() 空间复杂度:Θ()

棋盘dp三水兄弟——2853(本题)——1043(方格取数)——1169(传纸条)//MD一个解法吃完


by 25793 八月 3, 2016, 4:30 p.m.

Solution_ID:20259            四维只过一半,会爆空间,三维优化

                   时间复杂度:Θ() 空间复杂度:Θ((n^3))

/*优化方案:

我们首先来设计状态,用f[i][j][k]表示第k步时,

菜菜的路径在横坐标为i的区域,月月的路径在横坐标为j的格子上时,当前公平值的最大值。

这样三个值用来表示状态已经足够,因为菜菜和月月的位置可以用(i,k-i+1)和(j,k-j+1)来表示。

状态转移方程根据两人移动的方法设置如下:

f[i][j][k] = max{f[i-x][j-y][k-1]} + |a[i][k-i+1] - a[j][k-j+1]|,  x,y = 0,1}

 这样,本题就解决了,本题的时间复杂度为O(n3)。 */

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

int n,s;

int a[101][101],f[102][102][200];

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

 scanf("%d",&a[i][j]);

for(int k=1;k<2*n;k++)

{

for(int i=1;i<=n&&i<=k;i++)

{

for(int j=1;j<=n&&j<=k;j++)

{

   s=max(max(f[i-1][j][k-1],f[i][j-1][k-1]),max(f[i-1][j-1][k-1],f[i][j][k-1]));

   f[i][j][k]=s+abs(a[i][k-i+1]-a[j][k-j+1]);

   /*+1不能丢(走到第i行实际只走了i-1步,剩

下的要在列上加上(列也是从1开始,也是走了j-1步,不加的话就会从0开始))*/

}

}

}

printf("%d",f[n][n][2*n-1]);

}


by 42035 八月 2, 2016, 11:42 a.m.

Solution_ID:16617            Pascal

                   时间复杂度:Θ() 空间复杂度:Θ()

参考楼下C++版本改过来的,P党福利

program co1480;

uses math;

var f:array[0..200,0..105,0..105] of longint;

    a:array[0..100,0..100] of longint;

    step,i,j,n,sum,t:longint;


function max(x,y,z,w:longint):longint;

begin

  if x>y then max:=x else max:=y;

  if z>max then max:=z;

  if w>max then max:=w;

end;


begin

  readln(n);

  for i:=1 to n do

    begin

      for j:=1 to n do

        read(a[i,j]);

      readln;

    end;

  for step:=1 to 2*n-1 do

    begin

      if step>n then t:=n else t:=step;

      for i:=1 to t do

      for j:=1 to t do

        begin

          f[step,i,j]:=max(f[step-1,i-1,j],f[step-1,i-1,j-1],f[step-1,i,j-1],f[step-1,i,j]);

          sum:=abs(a[i,step-i+1]-a[j,step-j+1]);

          f[step,i,j]:=f[step,i,j]+sum;

        end;

    end;

  writeln(f[2*n-1,n,n]);

  readln;

end.


by 30961 二月 17, 2016, 11:03 a.m.

Solution_ID:16128            数据太水

                   时间复杂度:Θ(o(n^3)) 空间复杂度:Θ(o(n^3))

#include<cstdio>

#include<cstdlib>

#include<iostream>

using namespace std;

#define maxx(a,b,c,d) max(max(a,b),max(c,d))

int n;

int map[102][102];

int f[200][102][102];


int main()

{

scanf("%d",&n);

for(int i = 1;i <= n;++i)

for(int j = 1;j <= n;++j)

scanf("%d",&map[i][j]);


int p = 2 * n - 2;

for(int k = 1;k < p;++k)

{

for(int i = 1;i <= n && i <= k+1;++i)

for(int j = 1;j <= n && j <= k+1;++j)

if(i != j)f[k][i][j]=maxx(f[k-1][i][j],f[k-1][i-1][j],f[k-1][i][j-1],f[k-1][i-1][j-1]) + abs(map[i][k+2-i] - map[j][k+2-j]);

}

f[p][n][n]=maxx(f[p-1][n][n],f[p-1][n-1][n],f[p-1][n][n-1],f[p-1][n-1][n-1]);

cout << f[p][n][n];

return 0;

}


by 29774 一月 28, 2016, 9:16 p.m.

Solution_ID:13581            。。

                   时间复杂度:Θ() 空间复杂度:Θ()

http://www.ofsxb.com/archives/544


by 27864 十月 27, 2015, 3:34 p.m.

Solution_ID:12731            实际上与方格取数和传纸条一样

                   时间复杂度:Θ(o(n*n*n||n*n*n*n) 空间复杂度:Θ(o(n*n*n||n*n*n*n)

首先,大家应该都能自己写出四维动归,尽管会超出空间很多很多~~~

#include <cstdio>

#include <cstring>

#define fr(i,n) for(int i=1;i<=n;i++)

using namespace std;

int n,w[105][105],f[105][105][105][105];

int max(int a,int b)

{

    if(a<b)return b;else return a;

}

int ABS(int x)

{

if(x<0)return -x;else return x;

}

int main()

{

    scanf("%d",&n);

    fr(i,n)

        fr(j,n)

        scanf("%d",&w[i][j]);

    fr(i,n)

    fr(j,n)

    fr(k,n)

    fr(t,n)

    {

    f[i][j][k][t]=max(f[i-1][j][k-1][t],f[i][j][k][t]);

    f[i][j][k][t]=max(f[i-1][j][k][t-1],f[i][j][k][t]);

    f[i][j][k][t]=max(f[i][j-1][k-1][t],f[i][j][k][t]);

    f[i][j][k][t]=max(f[i][j-1][k][t-1],f[i][j][k][t]);

    f[i][j][k][t]+=ABS(w[i][j]-w[k][t]);

    }

    printf("%d",f[n][n][n][n]);

    return 0;

}

再其次,可以依靠步数,走到n,n点肯定会走n-1步来优化,就可以去掉俩个列的循环,但还要再加一个步数的循环,变成3维,就不会超空间了

#include <cstdio>

using namespace std;

int n,w[105][105],f[105][105][300];

int max(int a,int b)

{

if(a<b)return b;else return a;

}

int ABS(int x)

{

if(x<0)return -x;else return x;

}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

scanf("%d",&w[i][j]);

for(int k=1;k<n*2;k++)//按照步数优化

for(int i=1;i<=n&&i<=k;i++)

for(int j=1;j<=n&&j<=k;j++)

{

f[i][j][k]=max(f[i-1][j][k-1],f[i][j][k]);

f[i][j][k]=max(f[i-1][j-1][k-1],f[i][j][k]);

f[i][j][k]=max(f[i][j-1][k-1],f[i][j][k]);

f[i][j][k]=max(f[i][j][k-1],f[i][j][k]);

f[i][j][k]+=ABS(w[i][k-i+1]-w[j][k-j+1]);//+1不能丢(走到第i行实际只走了i-1步,剩下的要在列上加上(列也是从1开始,也是走了j-1步,不加的话就会从0开始))

}

printf("%d",f[n][n][2*n-1]);

return 0;

}


by 26344 十月 13, 2015, 10:02 p.m.

Solution_ID:626            DP

                   时间复杂度:O(n3) 空间复杂度:O(n3)

    本题是一道典型的动态规划题。

    我们首先来设计状态,用f[i][j][k]表示第i步时,菜菜的路径在横坐标为j的区域,月月的路径在横坐标为k的格子上时,当前公平值的最大值。这样三个值用来表示状态已经足够,因为菜菜和月月的位置可以用(j,i-j+1)和(k,i-k+1)来表示。

    状态转移方程根据两人移动的方法设置如下:

    f[i][j][k] = max{f[i-1][j-x][k-y]} + |a[j][i-j+1] - a[k][i-k+1]|,  x,y = 0,1}

    这样,本题就解决了,本题的时间复杂度为O(n3)。 


by 879 六月 2, 2013, 9:01 p.m.