1、传纸条
算法分析
image.png
利用
k == i1 + j1 == i2 + j2可优化到
时间复杂度 )
Java 代码
import java.util.Scanner;
public class Main {
static int N = 51;
static int n,m;
static int[][][][] f = new int[N][N][N][N];
static int[][] w = new int[N][N];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
{
w[i][j] = scan.nextInt();
}
}
for(int i1 = 1;i1 <= n;i1 ++)
{
for(int i2 = 1;i2 <= n;i2 ++)
{
for(int j1 = 1;j1 <= m;j1 ++)
{
for(int j2 = 1;j2 <= m;j2 ++)
{
int val = f[i1][j1][i2][j2];
int t = w[i1][j1];
if(i1 != i2 || j1 != j2) t += w[i2][j2];
val = Math.max(val, f[i1 - 1][j1][i2 - 1][j2] + t);
val = Math.max(val, f[i1 - 1][j1][i2][j2 - 1] + t);
val = Math.max(val, f[i1][j1 - 1][i2 - 1][j2] + t);
val = Math.max(val, f[i1][j1 - 1][i2][j2 - 1] + t);
f[i1][j1][i2][j2] = val;
}
}
}
}
System.out.println(f[n][m][n][m]);
}
}
2、乌龟方案
算法分析
image.png
注意：题目说到是从第一个格子开始往后跳，为了方便写代码，将第一个格子标记为0，因此若a1 + a2 * 2 + a3 * 3 + a4 * 4 == 0时，则表示是从w[0]转移过去的
时间复杂度
Java 代码
import java.util.Scanner;
public class Main {
static int N = 360,M = 41;
static int n,m;
static int[][][][] f = new int[M][M][M][M];
static int[] w = new int[N];
static int[] a = new int[5];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
for(int i = 0;i < n;i ++)
{
w[i] = scan.nextInt();
}
for(int i = 0;i < m;i ++)
{
int x = scan.nextInt();
a[x] ++;
}
for(int a1 = 0;a1 <= a[1];a1 ++)
{
for(int a2 = 0;a2 <= a[2];a2 ++)
{
for(int a3 = 0;a3 <= a[3];a3 ++)
{
for(int a4 = 0;a4 <= a[4];a4 ++)
{
int val = f[a1][a2][a3][a4];
int t = w[a1 + a2 * 2 + a3 * 3 + a4 * 4];
val = t;
if(a1 > 0) val = Math.max(val, f[a1 - 1][a2][a3][a4] + t);
if(a2 > 0) val = Math.max(val, f[a1][a2 - 1][a3][a4] + t);
if(a3 > 0) val = Math.max(val, f[a1][a2][a3 - 1][a4] + t);
if(a4 > 0) val = Math.max(val, f[a1][a2][a3][a4 - 1] + t);
f[a1][a2][a3][a4] = val;
}
}
}
}
System.out.println(f[a[1]][a[2]][a[3]][a[4]]);
}
}
3、摆渡车
算法分析
卡住了
